Keyakinan salah yang umum dalam ilmu komputer teoretis

EDIT AT 10/12/08:

Saya akan mencoba mengubah pertanyaan sehingga menarik minat lebih banyak orang untuk berbagi pendapat. Kami MEMBUTUHKAN kontribusi Anda!

Posting ini terinspirasi oleh yang ada di MO: Contoh keyakinan salah yang umum dalam matematika . Daftar besar kadang-kadang menghasilkan sejumlah besar jawaban yang kualitasnya sulit dikendalikan, tetapi setelah keberhasilan pos terkait di MO saya yakin bahwa akan sangat membantu untuk mendaftar sekelompok kepercayaan salah yang umum di TCS.

Namun, karena situs ini dirancang untuk menjawab pertanyaan tingkat penelitian, contoh-contoh seperti berarti waktu non-polinomial seharusnya tidak ada dalam daftar. Sementara itu, kami memang menginginkan beberapa contoh yang mungkin tidak sulit, tetapi tanpa memikirkannya secara terperinci, itu juga masuk akal. Kami ingin contoh-contohnya mendidik, dan biasanya muncul ketika mempelajari subjek pada saat pertama.$\mathsf{NP}$

Apa saja contoh (tidak sepele) dari kepercayaan salah yang umum dalam ilmu komputer teoretis, yang nampak bagi orang-orang yang belajar di bidang ini?

Lebih tepatnya, kami ingin contoh berbeda dari hasil yang mengejutkan dan hasil yang berlawanan dengan intuisi di TCS; hasil semacam ini membuat orang sulit untuk percaya, tetapi mereka BENAR. Di sini kami meminta contoh mengejutkan bahwa orang mungkin berpikir itu benar pada pandangan pertama, tetapi setelah berpikir lebih dalam, kesalahan di dalamnya terungkap.

Sebagai contoh jawaban yang tepat pada daftar, jawaban ini berasal dari bidang algoritma dan teori-grafik:

Untuk grafik $n$ -node $G$ , pemisah $k$ -edge $S$ adalah himpunan bagian dari ukuran $k$ , di mana node $G \setminus S$ dapat dipartisi menjadi dua bagian yang tidak berdekatan, masing-masing terdiri dari paling banyak $3n/4$ node . Kami memiliki lemma berikut":

Sebuah pohon memiliki pemisah 1-tepi.

Baik?

Ini adalah salah satu yang umum untuk geometri komputasi, tetapi endemik di tempat lain: Algoritma untuk RAM nyata dapat ditransfer ke RAM integer (untuk batasan integer masalah) tanpa kehilangan efisiensi. Sebuah contoh kanonik adalah klaim "Gaussian eliminasi berjalan pada waktu ." Faktanya, perintah eliminasi yang ceroboh dapat menghasilkan bilangan bulat dengan bit yang banyak secara eksponensial .$O(n^3)$

Lebih buruk lagi, tetapi sayangnya masih umum: Algoritma untuk RAM nyata dengan fungsi lantai dapat ditransfer ke RAM integer tanpa kehilangan efisiensi. Bahkan, RAM-nyata + lantai dapat memecahkan masalah di PSPACE atau di # P dalam sejumlah langkah polinomial .

Saya baru saja mendapatkan mitos lain yang rusak, yang disumbangkan oleh jawaban @ XXYYXX untuk posting ini :

• Masalah X adalah -Hard jika ada waktu polinomial (atau, logspace) pengurangan dari semua N P masalah untuk X.$\mathsf{NP}$$\mathsf{NP}$
• Asumsikan hipotesis waktu eksponensial, 3-SAT tidak memiliki algoritma waktu sub-eksponensial. Juga, 3-SAT adalah .$\mathsf{NP}$
• Jadi tidak ada masalah sulit X memiliki algoritma waktu sub-eksponensial. Kalau tidak, algoritma waktu sub-eksponensial untuk X + pengurangan waktu polinomial = algoritma waktu sub-eksponensial untuk 3-SAT.$\mathsf{NP}$

Tetapi kami memiliki algoritma waktu sub-eksponensial untuk beberapa masalah NP-hard.

Keyakinan keliru yang dipopulerkan tahun ini dan diceritakan berkali-kali ketika seseorang mencoba menjelaskan seluruh masalah , karena P dijelaskan sebagai efisien:$P \neq NP$$P$

"Jika , maka kita dapat memecahkan sejumlah besar masalah secara efisien. Jika tidak, kita tidak bisa"$P=NP$

Jika dapat diselesaikan dalam O ( n g o o g o l p l e x ) maka P = N P . Saya tidak berpikir ada orang yang berpikir untuk menjalankan algoritma ini.$3SAT$$O(n^{googolplex})$$P=NP$

Jika , kita masih dapat memiliki algoritma untuk T S P yang berjalan di n log ( log n ) , yang lebih kecil dari n 5 untuk n ≤ 2 32 . Kebanyakan orang akan sangat senang bisa menyelesaikan T S P untuk 4 miliar kota secepat itu.$P \neq NP$$TSP$$n^{\log(\log n)}$$n^{5}$$n\leq2^{32}$$TSP$

Ini benar-benar kepercayaan salah dalam matematika, tetapi sering muncul dalam konteks TCS: Jika variabel acak dan Y adalah independen, maka dikondisikan pada Z mereka tetap independen. (salah bahkan jika Z tidak tergantung pada X dan Y. )$X$$Y$$Z$$Z$$X$$Y$

Komputasi terdistribusi = komputasi kinerja tinggi terdistribusi (cluster, grid, cloud, seti @ home, ...).

Algoritma terdistribusi = algoritma untuk sistem ini.

Spoiler: Jika ini tidak terdengar seperti "keyakinan salah", saya sarankan Anda melihat konferensi seperti PODC dan DISC, dan melihat pekerjaan seperti apa yang orang lakukan ketika mereka mempelajari aspek teoritis dari komputasi terdistribusi.

Pengaturan masalah yang umum adalah sebagai berikut: Kami memiliki siklus dengan node; node diberi label dengan pengidentifikasi unik dari set { 1 , 2 , . . . , poli ( n ) } ; node bersifat deterministik dan bertukar pesan satu sama lain secara sinkron. Berapa banyak putaran komunikasi sinkron (sebagai fungsi dari n ) yang diperlukan untuk menemukan set independen maksimal? Berapa putaran yang diperlukan untuk menemukan set independen dengan setidaknya n / 1000 node? [Jawaban untuk kedua pertanyaan ini persis Θ ( log $n$$\{1,2,...,\text{poly}(n)\}$$n$$n/1000$ , ditemukan pada 1986–2008.]$\Theta(\log^* n)$

Artinya, orang sering mempelajari masalah yang benar-benar sepele dari perspektif algoritma terpusat, dan memiliki sedikit kesamaan dengan semua jenis superkomputer atau komputasi kinerja tinggi. Intinya tentu saja bukan mempercepat perhitungan terpusat dengan menggunakan lebih banyak prosesor, atau semacamnya.

Tujuannya adalah untuk membangun teori kompleksitas dengan mengklasifikasikan masalah grafik mendasar sesuai dengan kompleksitas komputasinya (misalnya, berapa banyak putaran sinkron yang diperlukan; berapa banyak bit yang ditransmisikan). Masalah seperti set independen dalam siklus mungkin tampak tidak ada gunanya, tetapi mereka melayani peran yang mirip dengan 3-SAT dalam komputasi terpusat: titik awal yang sangat berguna dalam pengurangan. Untuk aplikasi nyata di dunia nyata, lebih masuk akal untuk melihat perangkat seperti router dan sakelar di jaringan komunikasi, daripada komputer di grid dan cluster.

Keyakinan salah ini tidak sepenuhnya tidak berbahaya. Ini sebenarnya membuatnya cukup sulit untuk menjual karya yang berkaitan dengan teori algoritma terdistribusi kepada khalayak TCS umum. Saya telah menerima laporan wasit lucu dari konferensi TCS ...

Yang dasar, tetapi umum ketika kita pertama kali berurusan dengan notasi asimptotik. Pertimbangkan "bukti" berikut untuk relasi berulang dan T ( 1 ) = 1 :$T(n) = 2T(n/2) + O(n \log n)$$T(1) = 1$

Kami membuktikan dengan induksi. Untuk kasus dasar ini berlaku untuk . Anggap relasi berlaku untuk semua angka yang lebih kecil dari n ,$n=1$$n$

$\begin{align} T(n) &= 2 \cdot T(n/2) + O(n \log n) \\ &= 2 \cdot O(n/2 \log n/2) + O(n \log n) \\ &= O(n \log n/2) + O(n \log n) \\ &= O(n \log n) \\ \end{align}$

QED (kan?)

Sampai saat ini saya pikir bahwa setiap multi-pita Turing mesin yang berjalan dalam waktu T ( n ) dapat disimulasikan dengan dua pita menyadari Turing machinne M o dalam waktu O ( T ( n ) log T ( n ) ) sebagai berikut merasakan:$M$$T(n)$$M_o$$O(T(n)\log T(n))$

• pergerakan kepala 's hanya bergantung pada panjang masukan$M_o$
• untuk semua input dengan panjang yang sama, berhenti pada saat yang sama (yaitu Θ ( T ( n ) log T ( n ) ) ).$M_o$$\Theta(T(n)\log T(n))$

(lihat posting rjlipton ini misalnya)

Nah, baris kedua tidak berlaku secara umum, jika . Kita membutuhkan fungsi urutan waktu yang sepenuhnya dapat dibangun oleh waktu Θ ( T ( n ) log T ( n ) ) (lihat pertanyaan ini untuk definisi fungsi (sepenuhnya) yang dapat dikonstruksi waktu) atau kita perlu mengizinkan M o dijalankan untuk waktu yang tak terbatas (kami mengizinkan M o dijalankan setelah mencapai kondisi penerimaan di$EXP-TIME\neq NEXP-TIME$$\Theta(T(n)\log T(n))$$M_o$$M_o$ waktu). Masalahnya adalah, untuk T : N → N yang dapatdikonstruksikan secara umum,kami tidak dapat "mengukur" Θ ( T ( n ) log T ( n ) ) langkah waktu O ( T ( n ) log T ( n ) ) kecuali E X P - T I M $O(T(n)\log T(n))$$T:\mathbb{N}\rightarrow\mathbb{N}$$\Theta(T(n)\log T(n))$$O(T(n)\log T(n))$ .$EXP-TIME=NEXP-TIME$

Bukti dari klaim ini sangat mirip dengan bukti dalam jawaban Q1 di sini , jadi kami hanya akan memberikan ide-ide kunci.

Ambil masalah yang sewenang-wenang , L ⊆ { 0 , 1 } ∗ . Lalu ada sebuah k ∈ N , st L dapat diselesaikan oleh NDTM M di 2 n k langkah. Kita dapat mengasumsikan bahwa pada setiap langkah M masuk paling tidak dua negara yang berbeda untuk kesederhanaan. Selanjutnya, tentukan fungsi f ( n ) = { ( 8 n + $L\in NEXP-TIME$$L\subseteq\{0,1\}^*$$k\in\mathbb{N}$$L$$M$$2^{n^k}$$M$ Dapat dibuktikan bahwafadalah konstruksi waktu.

Sekarang anggaplah bahwa beberapa mesin Turing yang tidak disadari berjalan dalam waktu . Maka g sepenuhnya dapat dibangun waktu.$g(n)=\Theta(f(n)\log f(n))$$g$

Sekarang algoritma berikut memecahkan :$L$

• pada input , misalkan n menjadi angka dengan representasi biner x 00 ... 0 ( | x | k - 1 nol). Maka x = ( first  ⌊ k $x$$n$$x00\ldots 0$$|x|^{k-1}$.$x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$
• menghitung dalam waktu g ( n ) . Jika g ( n ) cukup besar, maka x ∈ L , lain x ∉ L . (ini hanya bekerja untuk cukup besar n . Berapa besar tergantung pada g .)$g(n)$$g(n)$$g(n)$$x\in L$$x\not\in L$$n$$g$

Algoritma ini berjalan dalam waktu eksponensial dan memecahkan . Sejak $L$ adalah sewenang-wenang, E X P - T I M E = N E X P - T I M E .$L\in NEXP-TIME$$EXP-TIME=NEXP-TIME$

Inilah dua sen saya:

Kelas kompleksitas , yang logspace acak , didefinisikan sebagai analog dari R P , yaitu, masalah keputusan yang dapat diselesaikan oleh non-deterministik mesin logspace M , di mana$\mathsf{RL}$$\mathsf{RP}$$M$

• untuk contoh positif, menerima dengan probabilitas setidaknya 1 / 2 ;$M$$1/2$
• untuk contoh negatif, menolak dengan probabilitas 1 .$M$$1$

Selanjutnya, mesin selalu berhenti.

Apakah definisi itu benar? (Tidak)

Misalkan dan g sepenuhnya fungsi yang dapat dibangun waktu (yaitu ada DTM yang pada input 1 n menghasilkan f ( n ) (resp. G $f$$g$$1^n$$f(n)$langkah-langkah n ) )dan biarkan f ( n + 1 ) = o ( g ( n ) ) .$g(n)$$f(n+1)=o(g(n))$

Hirarki waktu nondeterministik berkali- kali (secara dangkal) dinyatakan sebagai . (bukti: minta hierarki waktu nondeterministik dari Google).$NTIME(f(n))\subsetneq NTIME(g(n))$

Nah, hierarki sebenarnya hanya memberikan . Kita akan membutuhkan misalnya f ( n ) ≤ g ( n ) untuk n ) ) . Untuk fungsi f , g sedemikian sehingga f ( n + 1 ) = o $NTIME(g(n)) - NTIME(f(n))\neq\emptyset$$f(n)\leq g(n)$$NTIME(f(n))\subsetneq NTIME(g(n))$$f,g$ , f ( n ) ≤ g ( n ) sangat umum. Tetapi secara tegas, hierarki waktu nondeterministik sering kali dinyatakan secara dangkal.$f(n+1)=o(g(n))$$f(n)\leq g(n)$

Untuk menunjukkan bahwa tidak berlaku untuk semua sepenuhnya waktu-constructible f , g st f ( n + 1 ) = o ( g ( n ) ) , tentukan f ( n ) = { n + 1 n  ganjil$NTIME(f(n))\subseteq NTIME(g(n))$$f,g$$f(n+1)=o(g(n))$ dang(n)=f(n+1)2. Mudah untuk melihat bahwafdangsepenuhnya dapat dikonstruksikan secara waktu danf(n+1)=o(g(n)). Dari hierarki waktu nondeterministik kita tahu bahwa ada beberapa bahasaL∈NTIME((n+

Oleh karena itu . Mudah untuk melihat bahwa dari L 1 ∈ N T I M E ( g ( n ) ) mengikuti L ∈ N T I M E $L_1\in NTIME(f(n))$$L_1\in NTIME(g(n))$ , yang tidak benar. Oleh karena itu, L 1 ∈ N T I M $L\in NTIME((n+1)^2)$ .$L_1\in NTIME(f(n))-NTIME(g(n))$

Saya sudah sering mendengar itu menyatakan bahwa Valiant-Vazirani mengatakan bahwa acak mengurangi ke U P , atau bahwa $\mathsf{NP}$$\mathsf{UP}$ , atau bahwa N P ⊆ R ⋅ U P . Secara khusus, ini akan berarti bahwa jika Valiant-Vazirani bisa derandomized, maka N P = U P . Namun pada kenyataannya Valiant-Vazirani mengatakan bahwa N P ⊆ R P P r o m i s e U P .$\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{UP}}$$\mathsf{NP} \subseteq \mathsf{R} \cdot \mathsf{UP}$$\mathsf{NP}=\mathsf{UP}$$\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$

$\mathsf{UP}$$L$$x \in L$$\mathsf{US}$$\mathsf{US}$$\mathsf{UP}$$\mathsf{coNP} \subseteq \mathsf{US}$

$\mu$$X$$\{X=\mu\}$