Есть ли у coNP-complete проблемы субэкспоненциальный размер сертификата?

13

Если предположить, что NP! = CoNP, то для проблемы полного завершения coNP нет сертификата полиномиального размера. Но как насчет субэкспоненциального размера сертификата? Особенно для coSAT, есть ли субэкспоненциальное доказательство размера, чтобы доказать, что формула неудовлетворительна? Если нет, то каковы отрицательные доказательства? Благодарность

cc.complexity-theory proof-complexity Си Ву
источник

cstheory.stackexchange.com/questions/22022/…

Игорь Шинкарь,

12

Это тема доказательства сложности, т.е. размер сертификатов для задачи ( ). $\mathbf{co\text{-}NP}\text{-}complete$ $TAUT$ $= coSAT$

Краткий ответ: это открыто.

С отрицательной стороны, мы не можем даже показать , что не polysize опровержений для невыполнимых формул ( не говоря уже общий вопрос о том, показывая это для произвольной системы доказательств, пропозициональная систему доказательства можно рассматривать как недетерминированном алгоритм ). $Frege$ $TAUT$

Вопрос также эквивалентен . $\mathbf{coNP} \subseteq NTime(2^{o(n)})$

Кава
источник

1

Благодарю. Тогда каково общее убеждение в этой проблеме? Я предполагаю, что сообщество сделало некоторое "предположение" о результате.

Си Ву

У меня нет хорошего ответа, и я не помню, чтобы слышал догадки / догадки по этому поводу, единственное, что мне сейчас приходит в голову, это то, что некоторые эксперты считают вероятным, что EF (Extended-Frege) является оптимальным доказательством система, но EF как оптимальная система доказательств будет иметь смысл, даже если некоторые теоремы не имеют субэкспоненциальных EF-доказательств (т. е.

). Есть исследователи , которые находят даже

правдоподобно, и есть другие , которые думают , что

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)})$

Каве

7

Одним из возможных последствий этого будет то, что из результата Райана Уильяма (поскольку тогда у вас будет со-недетерминированный алгоритм для CircuitSAT, работающий во времени быстрее, чем экспоненциальный). Не совсем негативные доказательства, но все же ... $NEXP \nsubseteq P/poly$

Ramprasad
источник

Благодарю. Я склонен истолковывать ваш ответ, поскольку трудность показать, что проблема, полная coNP, имеет субэкспоненциальное доказательство размера, потому что тогда у нас будет хорошее разделение.

Си Ву

Есть ли у coNP-complete проблемы субэкспоненциальный размер сертификата?

Ответы: