O problema de coNP-complete possui certificado de tamanho subexponencial?

13

Assumindo NP! = CoNP, não há certificado de tamanho polinomial para o problema de coNP-completo. Mas e o certificado de tamanho subexponencial? Particularmente para coSAT, existe uma prova subexponencial de tamanho para provar que uma fórmula é insatisfatória? Caso contrário, qual é a evidência negativa? obrigado

cc.complexity-theory proof-complexity Xi Wu
fonte

cstheory.stackexchange.com/questions/22022/…

Igor Shinkar

12

Este é o tema da complexidade prova, ou seja, o tamanho de certificados para o $\mathbf{co\text{-}NP}\text{-}complete$ problema $TAUT$ ( $= coSAT$ ).

A resposta curta é: está aberta.

No lado negativo, não podemos ainda mostrar que não são polysize refutações para fórmulas insatisfatível (e muito menos a questão geral de mostrar isso para um sistema à prova arbitrária, um sistema à prova proposicional pode ser pensado como um algoritmo não determinístico para ). $Frege$ $TAUT$

A questão é também equivalente a . $\mathbf{coNP} \subseteq NTime(2^{o(n)})$

Kaveh
fonte

1

Obrigado. Então, qual é a crença geral para esse problema? Eu acho que a comunidade fez um "palpite" sobre o resultado.

Xi Wu

Não tenho uma boa resposta e não me lembro de ouvir conjecturas / suposições sobre isso, a única coisa relacionada que me vem à mente agora é que alguns especialistas acham plausível que a EF (Extended-Frege) seja uma prova ideal sistema, mas EF sendo um sistema de prova ideal faria sentido, mesmo se alguns teoremas não tiverem provas subexponenciais de EF (por exemplo,

). Existem pesquisadores que consideram plausíveis e outros pensam que ).

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

Uma possível implicação disso seria que o do resultado de Ryan William (já que você teria um algoritmo co-não-determinístico para o CircuitSAT executando mais rápido que o exponencial). Não é uma evidência realmente negativa, mas ainda assim ... $NEXP \nsubseteq P/poly$

Ramprasad
fonte

Obrigado. Inclino-me a interpretar sua resposta como a dificuldade de mostrar que o problema de coNP-completo tem uma prova de tamanho subexponencial, porque temos uma boa separação.

Xi Wu

O problema de coNP-complete possui certificado de tamanho subexponencial?

Respostas: