Konsekuensi dari dan ?

Kita tahu bahwa jika maka seluruh PH akan runtuh. Bagaimana jika hierarki polinomial runtuh sebagian? (Atau bagaimana memahami bahwa PH dapat runtuh di atas titik tertentu dan tidak di bawah?)$P=NP$

Dengan kata yang lebih singkat, apa yang akan menjadi konsekuensi dari dan ?P ≠ N $NP=coNP$$P\ne NP$

Bagi saya, salah satu konsekuensi paling mendasar dan mengejutkan dari adalah adanya bukti singkat untuk sejumlah besar masalah di mana sangat sulit untuk melihat mengapa mereka harus memiliki bukti singkat. (Ini semacam mundur dari "Apa implikasi kompleksitas lain yang dimiliki keruntuhan ini?" Ke "Apa alasan yang paling mendasar dan sederhana yang menyebabkan keruntuhan ini mengejutkan?")$\mathsf{NP}=\mathsf{coNP}$

Misalnya, jika , maka untuk setiap grafik yang bukan Hamilton, ada bukti singkat tentang fakta itu. Demikian pula untuk grafik yang tidak 3-warna. Demikian pula untuk pasangan grafik yang tidak isomorfik. Demikian pula untuk setiap tautologi proposisional .$\mathsf{NP}=\mathsf{coNP}$

Di dunia di mana , kesulitan dalam membuktikan tautologi proposisional bukan karena beberapa tautologi pendek memiliki bukti panjang - karena di dunia seperti itu setiap tautologi memiliki polinomi bukti singkat - tetapi ada beberapa alasan lain mengapa kami tidak dapat menemukan bukti tersebut secara efisien.$\mathsf{P} \neq \mathsf{NP} = \mathsf{coNP}$

Jika kita juga mengasumsikan , maka hipotesis juga akan menyebabkan runtuhnya kelas acak: . Meskipun ini semua diduga terkondisikan untuk runtuh tanpa syarat ke , bagaimanapun, masih terbuka apakah itu memang terjadi. Bagaimanapun, tampaknya tidak menyiratkan bahwa kelas-kelas acak ini runtuh.$\mathsf{NP}=\mathsf{RP}$P N P = c o N $\,\,\mathsf{ZPP}=\mathsf{RP}=\mathsf{CoRP}=\mathsf{BPP}$$\mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$

Jika tidak, artinya, kita setidaknya memiliki , maka, bersama dengan , ini akan memiliki hal penting lainnya. konsekuensi: . Ini mengikuti dari hasil Babai, Fortnow, Nisan dan Wigderson, yang mengatakan bahwa jika semua bahasa unary (tally) dalam masuk dalam , maka . Dengan demikian, jika , maka mereka tidak dapat semuanya masuk dalam , karena menyiratkan$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$$\,\,\mathsf{E}\neq \mathsf{NE}$$\mathsf{PH}$$\mathsf{P}$$\mathsf{BPP}=\mathsf{P}$$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$$\mathsf{PH}=\mathsf{NP}$. Oleh karena itu, harus ada bahasa penghitungan di . Akhirnya, kehadiran bahasa penghitungan di dikenal dengan baik menyiratkan .$\mathsf{NP}-\mathsf{P}$$\mathsf{NP}-\mathsf{P}$$\mathsf{E}\neq \mathsf{NE}$

Alasan di atas menunjukkan efek menarik bahwa , meskipun runtuh, sebenarnya memperkuat kekuatan pemisahan , seperti yang terakhir sendiri tidak diketahui menyiratkan . "Anomali" ini tampaknya mendukung dugaan .B P P ≠ P E ≠ N E B P P = $\mathsf{NP}=co\mathsf{NP}$$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{E}\neq \mathsf{NE}$$\mathsf{BPP}= \mathsf{P}$

${\bf \#P}$

${ \rm \underline {Valiant's-Definition:}}$$C$$\#C =\cup_{A\in C}(\#P)^{A}$$({\#P}^A)$$A$

${\bf \#NP} = {\bf \#CoNP}$

${ \rm \underline {Toda's-Definition:}}$$C$$\# .C$$f$$C-$$R$$p$$x$$f(x)=||\{y|p(|x|)=|y|$$R(x,y)\}||$

${\bf \#.NP} = {\bf \#.CoNP}$${\bf NP} = {\bf CoNP}$

${\bf P}\not = {\bf NP}$${\bf FP} \not = {\bf \# P}$

Ker-i Ko Menunjukkan bahwa ada oracle yang membuat PH runtuh di tingkat k-th. Lihat "Ker-I Ko: Relativized Polynomial Time Hierarchies Memiliki K Level Yang Tepat. SIAM J. Comput. 18 (2): 392-408 (1989)".