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

Odpowiedzi:

12

Jest to temat złożoności dowodu, tj. Wielkości certyfikatów dla problemu ( ).T A U T = c o S A Tco-NP-completeTAUT=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 ).T A U TFregeTAUT

Pytanie jest również równoważne z .coNP⊆NTime(2o(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 P c o N P ⊈ N T i m e ( 2 o ( n ) )coNP⊈NTime(2o(n))coNP=NPcoNP⊈NTime(2o(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⊈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