Apakah masalah selesai-TNP memiliki sertifikat ukuran subeksponensial?

13

Dengan asumsi NP! = CoNP, maka tidak ada sertifikat ukuran polinomial untuk masalah lengkap-TNP. Tapi bagaimana dengan sertifikat ukuran subeksponensial? Khususnya untuk coSAT, adakah bukti ukuran subeksponensial untuk membuktikan formula tidak memuaskan? Jika tidak, apa bukti negatifnya? Terima kasih

cc.complexity-theory proof-complexity Xi Wu
sumber

cstheory.stackexchange.com/questions/22022/…

Igor Shinkar

12

Ini adalah topik kompleksitas bukti, yaitu ukuran sertifikat untuk masalah ( ). $\mathbf{co\text{-}NP}\text{-}complete$ $TAUT$ $= coSAT$

Jawaban singkatnya adalah: terbuka.

Di sisi negatif, kita bahkan tidak bisa menunjukkan bahwa ada tidak polysize bantahan-bantahan untuk formula unsatisfiable (apalagi pertanyaan umum menunjukkan ini untuk sistem bukti sewenang-wenang, sistem pembuktian proposisi dapat dianggap sebagai algoritma nondeterministic untuk ). $Frege$ $TAUT$

Pertanyaannya juga setara dengan . $\mathbf{coNP} \subseteq NTime(2^{o(n)})$

Kaveh
sumber

1

Terima kasih. Lalu apa kepercayaan umum untuk masalah ini? Saya kira komunitas telah membuat "tebakan" tentang hasilnya.

Xi Wu

Saya tidak memiliki jawaban yang baik dan saya tidak ingat pernah mendengar dugaan / dugaan tentang hal ini, satu-satunya hal terkait yang muncul di pikiran saya saat ini adalah bahwa beberapa ahli berpendapat bahwa EF (Extended-Frege) adalah bukti yang optimal sistem, tetapi EF menjadi sistem bukti yang optimal akan masuk akal bahkan jika beberapa teorema tidak memiliki bukti EF subexponential (yaitu

). Ada peneliti yang menemukan bahkan

masuk akal, dan ada juga yang berpikir

c o N P ⊈ N T i m e (2^{o (n)})

$\mathbf{coNP} \not \subseteq NTime(2^{o(n)})$

c o N P = N P

$\mathbf{coNP}=\mathbf{NP}$

).

c o N P ⊈ N T i m e (2^{o (n)})

$\mathbf{coNP} \not \subseteq NTime(2^{o(n)})$

Kaveh

7

Salah satu implikasi yang mungkin dari hal ini adalah bahwa dari hasil Ryan William (karena Anda kemudian akan memiliki algoritma co-nondeterministic untuk CircuitSAT yang berjalan dalam waktu lebih cepat daripada eksponensial). Bukan bukti yang benar-benar negatif, tapi tetap saja ... $NEXP \nsubseteq P/poly$

Ramprasad
sumber

Terima kasih. Saya cenderung menafsirkan jawaban Anda karena kesulitan untuk menunjukkan masalah selesai-TNP memiliki bukti ukuran subeksponensial, karena kami memiliki pemisahan yang bagus.

Xi Wu

Apakah masalah selesai-TNP memiliki sertifikat ukuran subeksponensial?

Jawaban: