Penjelasan teoretis apa yang ada untuk keberhasilan praktis pemecah SAT, dan dapatkah seseorang memberikan ikhtisar dan penjelasan "gaya-wikipedia" yang mengikat semuanya? Secara analogi, analisis yang dihaluskan ( versi arXiv )) untuk algoritme simpleks melakukan pekerjaan yang hebat...
Adakah manfaat untuk menghitung kompleksitas waktu suatu algoritma menggunakan lambda calculus? Atau adakah sistem lain yang dirancang untuk tujuan ini? Referensi apa pun akan
Dapatkah seseorang memberikan penjelasan singkat tentang pendekatan GCT Mulmuley yang dapat dimengerti oleh non-pakar? Penjelasan yang cocok untuk halaman Wikipedia tentang topik tersebut (yang saat ini belum selesai). Motivasi: Saya "membaca bersama" buku Scott Aaronson Quantum Computing sejak...
Di utas lain , Joe Fitzsimons bertanya tentang "batas bawah terbaik saat ini pada 3SAT." Saya ingin pergi ke arah lain: Apa batas atas terbaik saat ini di 3SAT? Dengan kata lain, apa kompleksitas waktu dari pemecah SAT yang paling efisien? Secara khusus, apakah mungkin untuk menemukan algoritma...
Saya memikirkan masalah berikut: Saya ingin menemukan ekspresi reguler yang cocok dengan serangkaian string tertentu (misalnya, alamat email yang valid) dan tidak cocok dengan yang lain (alamat email yang tidak valid). Misalkan dengan ekspresi reguler yang kami maksud adalah mesin negara terbatas...
Terinspirasi oleh pertanyaan ini dan khususnya paragraf terakhir dari jawaban Or, saya memiliki pertanyaan berikut: Apakah Anda tahu ada aplikasi dari teori representasi kelompok simetris di TCS? Grup simetris adalah grup dari semua permutasi dari dengan komposisi operasi grup. Representasi...
Komputer nyata memiliki memori yang terbatas dan hanya sejumlah negara terbatas. Jadi mereka pada dasarnya automata terbatas. Mengapa ilmuwan komputer teoretis menggunakan mesin Turing (dan model lain yang setara) untuk mempelajari komputer? Apa gunanya mempelajari model yang jauh lebih kuat ini...
Tampak jelas bahwa sejumlah subbidang ilmu komputer teoretis telah secara signifikan dipengaruhi oleh hasil-hasil dari teori fisika. Dua contohnya adalah Perhitungan kuantum Hasil mekanika statistik digunakan dalam analisis kompleksitas / algoritma heuristik. Jadi pertanyaan saya, adakah bidang...
Saat ini saya sedang menulis survei tentang teorema hierarki di TCS. Mencari makalah terkait saya perhatikan bahwa hierarki adalah konsep fundamendal tidak hanya dalam TCS dan matematika, tetapi dalam berbagai ilmu, dari teologi dan sosiologi ke biologi dan kimia. Melihat jumlah informasinya sangat...
Di MathOverflow, Timothy Gowers mengajukan pertanyaan berjudul " Mendemonstrasikan kekakuan itu penting ". Sebagian besar diskusi di sana tentang kasus-kasus yang menunjukkan pentingnya pembuktian, yang mungkin tidak perlu diyakinkan oleh orang-orang di CSTheory. Dalam pengalaman saya bukti perlu...
Saya seorang mahasiswa tahun ke 2 dalam teori. Saya telah mengerjakan masalah selama setahun terakhir (dalam teori graf / algoritma). Sampai kemarin saya pikir saya baik-baik saja (saya memperpanjang teorema dari kertas). Hari ini saya menyadari bahwa saya telah membuat kesalahan sederhana. Saya...
Pada 1937 Turing menggambarkan mesin Turing. Sejak itu banyak model komputasi telah diuraikan dalam upaya untuk menemukan model yang seperti komputer nyata tetapi masih cukup sederhana untuk merancang dan menganalisis algoritma. Akibatnya, kami memiliki selusin algoritma untuk, misalnya, masalah...
Bidang komputasi terdistribusi telah gagal dalam mengembangkan teori matematika tunggal untuk menggambarkan algoritma terdistribusi. Ada beberapa 'model' dan kerangka kerja komputasi terdistribusi yang sama sekali tidak kompatibel satu sama lain. Ledakan semata-mata dari berbagai sifat temporal...
Saya ingin memahami Applicativedalam hal teori kategori. The dokumentasi untuk Applicativemengatakan bahwa itu functor longgar monoidal kuat . Pertama, Wikipedia halaman tentang functors monoidal mengatakan bahwa functor monoidal adalah baik longgar atau kuat . Jadi menurut saya salah satu sumber...
Ini adalah pertanyaan yang terkait dengan yang ini . Menempatkannya kembali dalam bentuk yang lebih sederhana setelah banyak diskusi di sana, yang rasanya seperti pertanyaan yang sama sekali berbeda. Bukti klasik dari ketidakpastian masalah penghentian tergantung pada menunjukkan kontradiksi...
Meskipun sudah beberapa tahun kuliah, saya masih bingung memilih topik penelitian. Saya telah mencari kertas dari berbagai daerah dan berbicara dengan profesor, dan saya mulai berpikir ini adalah pendekatan yang salah. Saya pernah membaca bahwa ini membantu untuk menemukan masalah yang menarik...
Dapatkah setiap fungsi yang dapat dihitung dalam waktu pada mesin Turing pita tunggal menggunakan alfabet ukuran dapat dihitung dalam waktu pada mesin Turing single-tape menggunakan alfabet ukuran (katakanlah, dan kosong)?f:{0,1}∗→{0,1}f:{0,1}∗→{0,1}f : \{0,1\}^* \to \{0,1\}tttk=O(1)k=O(1)k =...
Latar Belakang Perhitungan atas bilangan real lebih rumit daripada perhitungan atas bilangan alami, karena bilangan real adalah objek tak terhingga dan ada banyak bilangan real, oleh karena itu bilangan real tidak dapat dengan setia diwakili oleh string berhingga pada alfabet terbatas. Berbeda...
Ini adalah pertanyaan tentang kompleksitas rangkaian. (Definisi ada di bawah.) Yao dan Beigel-Tarui menunjukkan bahwa setiap rangkaian keluarga dari ukuran s memiliki keluarga rangkaian yang setara dengan ukuran s p o l y ( log s ) dari kedalaman dua , di mana gerbang keluaran adalah fungsi...
Masalah Graph Isomorphism (GI) bisa dibilang kandidat yang paling dikenal untuk masalah NP-intermediate . Algoritma yang paling dikenal adalah algoritma sub-eksponensial dengan run-time . Diketahui bahwa GI bukan-complete kecualihierarki polinomialnyaruntuh.2O ( n logn√)2O(nlogn)2^{O(\sqrt{n \log...