L / P / PSpace vs P / NP

pada tahun 1979 Hopcroft / Ullman menulis bahwa L ⊆ P ⊆ NP ⊆ PSpace diketahui tetapi L ⊊ PSpace adalah satu-satunya penahanan yang tepat (& sepele) yang diketahui meskipun semua dikira sebagai penahanan yang tepat, dan "di mana keadaan masih ada" ~ 4 dekade kemudian .

sejak itu apakah ada hubungan yang diketahui antara L ⊊ P, P ⊊ PSpace dan P ⊊ NP? apakah mereka semua masih dianggap independen, atau adakah tanda-tanda saling ketergantungan?

motivasi: pertanyaan ini sebagian terinspirasi oleh hasil Backurs-Indyk baru-baru ini yang mengaitkan SETH dengan O (n ² ) sunting jarak. SETH adalah waktu yang eksponensial dan jarak pengeditan adalah PTime. (& juga pertanyaan yang membuktikan batas bawah dengan membuktikan batas atas )

Satu-satunya penahanan yang tepat yang diketahui masih $L \subsetneq PSPACE$ , meskipun semuanya diyakini berbeda. Semua sisanya masih terbuka lebar.

Karya terbaru tentang `` Fine-Grained Complexity ", seperti hasil Edit Distance dari Backurs dan Indyk, menyampingkan fakta bahwa kami tidak dapat membuktikan penahanan yang tepat, seperti . Secara khusus, SETH jauh lebih kuat dugaan dari , lebih atau kurang menyatakan bahwa CNF-SAT membutuhkan waktu (bukan hanya waktu super polinomial) .Di bawah dugaan yang lebih kuat ini, jika Anda dapat menunjukkan pengurangan dari CNF- SAT untuk masalah dalam (seperti Edit Distance), maka Anda mendapatkan batas bawah bersyarat berdasarkan SETH. Jadi, perbedaan yang dikerjakan oleh karya-karya ini sendiri (yaitu vs.$P\neq NP$$P \neq NP$$2^n$$2^{n/k}$$P$$\Omega(n^k)$$2^{n}$$2^{(1-\delta)n}$) jauh lebih ketat daripada perbedaan antara kelas kompleksitas tradisional yang disebutkan dalam posting.

Demikian pula, dalam membuktikan batas bawah sirkuit dengan memberikan algoritme kepuasan yang lebih cepat, kita umumnya hanya memerlukan peningkatan berbutir halus atas algoritme yang sepele untuk memberikan batas yang lebih rendah. Sebagai contoh, algoritma untuk CircuitSAT pada sirkuit gates akan membuktikan .2 n p o l y ( n k ) / n ω ( 1 ) n k N E X P ⊈ P / p o l $O^\star(2^n)$$2^{n}poly(n^k)/n^{\omega(1)}$$n^k$$NEXP \not \subseteq P/poly$