Czy problem z ukończeniem koNP ma podwykonawczy certyfikat rozmiaru?

13

Zakładając, że NP! = CoNP, to nie ma certyfikatu wielomianu dla problemu pełnego coNP. Ale co z podwykładniczym certyfikatem wielkości? Czy w szczególności w przypadku coSAT istnieje podwykładniczy dowód wielkości, aby udowodnić, że formuła jest niezadowalająca? Jeśli nie, jakie są negatywne dowody? Dzięki

cc.complexity-theory proof-complexity

— Xi Wu
źródło

cstheory.stackexchange.com/questions/22022/…

— Igor Shinkar

12

Jest to temat złożoności dowodu, tj. Wielkości certyfikatów dla problemu ( ). $\mathbf{co\text{-}NP}\text{-}complete$ $TAUT$ $= coSAT$

Krótka odpowiedź brzmi: jest otwarta.

Po stronie negatywnej, nie możemy nawet pokazać, że nie są polysize refutations dla wzorów unsatisfiable (nie mówiąc już o ogólną kwestię pokazując to dla dowolnego systemu dowodu, propositional System dowodem mogą być traktowane jako niedeterministycznych algorytmu ). $Frege$ $TAUT$

Pytanie jest również równoważne z . $\mathbf{coNP} \subseteq NTime(2^{o(n)})$

— Kaveh
źródło

1

Dzięki. Jakie jest zatem ogólne przekonanie o tym problemie? Wydaje mi się, że społeczność „zgadła” na temat wyniku.

— Xi Wu

Nie mam dobrej odpowiedzi i nie pamiętam, że słyszałem przypuszczenia / domysły na ten temat, jedyną pokrewną rzeczą, która przychodzi mi teraz na myśl, jest to, że niektórzy eksperci uważają za prawdopodobne, że EF (Extended-Frege) jest optymalnym dowodem system, ale EF jako optymalny system dowodowy miałby sens, nawet jeśli niektóre twierdzenia nie mają podwykładniczych dowodów EF (tj. ). Są badacze, którzy uważają, że nawet wiarygodny, i są inni, którzy myślą, że ).

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

Jedną z możliwych implikacji tego byłoby to, że z wyniku Ryana Williama (ponieważ miałbyś wtedy algorytm ko-niedeterministyczny dla CircuitSAT działającego w czasie szybszym niż wykładniczy). Niezbyt negatywne dowody, ale wciąż ... $NEXP \nsubseteq P/poly$

— Ramprasad
źródło

Dzięki. Skłaniam się do zinterpretowania twojej odpowiedzi, ponieważ trudność w wykazaniu, że problem z całkowitym koNP ma podwykładniczy dowód wielkości, ponieważ wtedy mamy dobrą separację.

— Xi Wu