Baru-baru ini, seorang teman saya (bekerja di TCS) menyebutkan dalam sebuah percakapan bahwa "dia ingin melihat / mengetahui semua (atau sebanyak mungkin) hasil indah di TCS dalam hidupnya". Jenis ini membuat saya bertanya-tanya tentang hasil yang indah di bidang ini dan karenanya motivasi untuk...
Apakah ada bahasa pemrograman (fungsional?) Di mana semua fungsi memiliki bentuk kanonik? Yaitu, setiap dua fungsi yang mengembalikan nilai yang sama untuk semua rangkaian input direpresentasikan dengan cara yang sama, misalnya jika f (x) mengembalikan x + 1, dan g (x) mengembalikan x + 2, maka f...
Diketahui oleh Teorema Ladner bahwa jika , maka ada banyak -intermediate ( ) yang tak terhingga jumlahnya . Ada juga kandidat alami untuk status ini, seperti Grafik Isomorfisme, dan sejumlah lainnya, lihat Masalah Antara P dan NPC . Namun demikian, sebagian besar di antara kerumunan yang dikenal...
Diketahui bahwa dengan seperangkat algoritma yang dapat dihitung (dicirikan oleh nomor Gödel), kita tidak dapat menghitung (membangun algoritma biner yang memeriksa kepemilikan) semua himpunan bagian dari N. Sebuah bukti dapat diringkas sebagai: jika kita bisa, maka himpunan semua himpunan bagian...
NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}P ≠ N P N P I : = N P ∖ ( N P C ∪ P ) ≠ ∅ P / poli N P I ⊂ P / poli N P ⊂ N P C ∪ P / poliPH=Σ2PH=Σ2\mathsf{PH} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne \mathsf{NP}NPI:=NP∖(NPC∪P)≠∅NPI:=NP∖(NPC∪P)≠∅\mathsf{NPI} := \mathsf{NP}...
Sangat mudah untuk melihat bahwa grafik isomorfisma (GI) dalam NP. Ini adalah masalah terbuka utama apakah GI ada dalam coNP. Apakah ada kandidat potensial dari properti grafik yang dapat digunakan sebagai sertifikat coNP dari GI. dugaan yang menyiratkan ? Apa saja implikasi dari ?G I ∈ c o N PG I∈...
Dalam satu kalimat: apakah akan ada hierarki untuk menyiratkan hasil derandomisasi?BPTIMEBPTIME\mathsf{BPTIME} Pertanyaan yang terkait tetapi tidak jelas adalah: apakah keberadaan hierarki untuk menyiratkan adanya batas bawah yang sulit? Apakah resolusi masalah ini menabrak penghalang yang dikenal...
Ada dua pertanyaan yang diajukan baru-baru ini di cs.se yang terkait atau memiliki kasus khusus yang setara dengan pertanyaan berikut: Misalkan Anda memiliki urutan dari n angka sehingga Σ n i = 1 a i = n ( n + 1 ) . Uraikan menjadi jumlah dari dua permutasi, π dan σ , dari 1 ... n , sehingga a i...
Misalkan P = NP benar. Apakah kemudian akan ada aplikasi praktis untuk membangun komputer kuantum seperti memecahkan masalah tertentu lebih cepat, atau akankah perbaikan seperti itu menjadi tidak relevan berdasarkan fakta bahwa P = NP benar? Bagaimana Anda mengkarakterisasi peningkatan efisiensi...
Komputer yang diberi aliran tak terbatas dari bit yang benar-benar acak lebih kuat daripada komputer tanpa itu. Pertanyaannya adalah: apakah ini cukup kuat untuk menyelesaikan masalah penghentian? Artinya, dapatkah komputer probabilistik menentukan apakah suatu program deterministik berhenti atau...
Biarkan menjadi fungsi Boolean dan mari kita pikirkan f sebagai fungsi dari hingga \ {-1,1 \} . Dalam bahasa ini, ekspansi Fourier dari f hanyalah perluasan dari f dalam hal monomial bebas persegi. ( 2 ^ monomial ini membentuk dasar ruang fungsi nyata pada \ {- 1,1 \} ^ n . Jumlah kuadrat dari...
Masalah berikut muncul selama penelitian, dan ternyata sangat bersih: Anda memiliki sumber koin. Setiap koin memiliki bias, yaitu probabilitas bahwa koin itu jatuh di atas "kepala". Untuk setiap koin secara mandiri ada probabilitas 2/3 bahwa ia memiliki bias setidaknya 0,9, dan dengan sisa...
Saya telah mendengar bahwa ada argumen heuristik dalam fisika statistik yang menghasilkan hasil dalam teori probabilitas di mana bukti yang kuat tidak diketahui atau sangat sulit untuk dicapai. Apa contoh mainan sederhana dari fenomena seperti itu? Akan lebih baik jika jawabannya diasumsikan...
Saya seorang pemula yang bekerja pada metode yang membuktikan kesetaraan program. Saya telah membaca beberapa makalah tentang mendefinisikan hubungan logis atau simulasi untuk membuktikan bahwa dua program setara. Tetapi saya cukup bingung tentang dua teknik ini. Saya hanya tahu hubungan logis...
Ini adalah pertanyaan lanjutan untuk Apa perbedaan antara bukti dan program (atau antara proposisi dan tipe)? Program apa yang sesuai dengan bukti non-konstruktif (klasik) dari bentuk ∀k T(e,k)∨¬∀k T(e,k)∀k T(e,k)∨¬∀k T(e,k)\forall k \ T(e,k) \lor \lnot \forall k \ T(e,k) ? (Asumsikan bahwa TTT...
Algoritma klasik dapat menyelesaikan 3-SAT dalam waktu (acak) atau 1,3303 n waktu (deterministik). (Referensi: Batas Atas Terbaik di SAT )1.3071n1.3071n1.3071^n1.3303n1.3303n1.3303^n Sebagai perbandingan, menggunakan algoritma Grover pada komputer kuantum akan mencari dan memberikan solusi dalam ,...
Kompleksitas terobosan terobosan baru-baru ini hasil bawah dari Ryan Williams memberikan teknik bukti yang menggunakan hasil batas atas untuk membuktikan kompleksitas batas bawah. Suresh Venkat dalam jawabannya untuk pertanyaan ini, Apakah ada hasil kontra-intuitif dalam ilmu komputer teoretis? ,...
Sebuah string memiliki urutan, tetapi biasanya tidak semuanya berbeda. Apa kompleksitas menemukan frekuensi maksimum dari setiap urutan?2n2n2^n Sebagai contoh, string "urutan" berisi 7 salinan dari urutan "menuntut" dan ini adalah maksimum. Contoh kode brute-force di
Posting blog Scott Aaronson hari ini memberikan daftar masalah / tugas terbuka yang menarik dalam kompleksitas. Seseorang khususnya menarik perhatian saya: Bangun perpustakaan umum dengan instance 3SAT, dengan sesedikit mungkin variabel dan klausa, yang akan memiliki konsekuensi penting jika...
Pertimbangkan automata terbatas nondeterministic , dan fungsi . Selain itu kami mendefinisikan .A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F)f(n)f(n)f(n)Σ≤k=⋃i≤kΣiΣ≤k=⋃i≤kΣi\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i Sekarang mari kita menganalisis pernyataan berikut: Jika ,...