¿El problema coNP-complete tiene un certificado de tamaño subexponencial?

13

Suponiendo que NP! = CoNP, entonces no hay un certificado de tamaño polinómico para el problema de coNP completo. ¿Pero qué pasa con el certificado de tamaño subexponencial? Particularmente para coSAT, ¿hay una prueba de tamaño subexponencial para demostrar que una fórmula no es satisfactoria? Si no, ¿cuál es la evidencia negativa? Gracias

cc.complexity-theory proof-complexity Xi Wu
fuente

cstheory.stackexchange.com/questions/22022/…

Igor Shinkar

12

Este es el tema de complejidad prueba, es decir el tamaño de certificados para el problema ( ). $\mathbf{co\text{-}NP}\text{-}complete$ $TAUT$ $= coSAT$

La respuesta corta es: está abierto.

En el lado negativo, ni siquiera podemos demostrar que no están polysize refutaciones para las fórmulas unsatisfiable (por no hablar de la cuestión general de mostrar esto para un sistema de prueba arbitraria, un sistema a prueba de proposiciones puede ser pensado como un algoritmo determinista para ). $Frege$ $TAUT$

La pregunta también es equivalente a . $\mathbf{coNP} \subseteq NTime(2^{o(n)})$

Kaveh
fuente

1

Gracias. Entonces, ¿cuál es la creencia general de este problema? Supongo que la comunidad ha hecho algunas "suposiciones" sobre el resultado.

Xi Wu

No tengo una buena respuesta y no recuerdo haber escuchado conjeturas / conjeturas sobre esto, lo único que se me ocurre en este momento es que algunos expertos consideran plausible que EF (Extended-Frege) sea una prueba óptima sistema, pero EF es un sistema de prueba óptimo tendría sentido incluso si algunos teoremas no tienen pruebas EF subexponenciales (es decir,

). Hay investigadores que consideran plausible incluso

, y hay otros que piensan 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

Una posible implicación de esto sería que del resultado de Ryan William (ya que entonces tendría un algoritmo co-no determinista para CircuitSAT funcionando a tiempo más rápido que exponencial). No es una evidencia realmente negativa, pero aún así ... $NEXP \nsubseteq P/poly$

Ramprasad
fuente

Gracias. Me inclino a interpretar su respuesta ya que la dificultad para mostrar el problema de coNP completo tiene una prueba de tamaño subexponencial, porque entonces tenemos una buena separación.

Xi Wu

¿El problema coNP-complete tiene un certificado de tamaño subexponencial?

Respuestas: