Le problème coNP-complete a-t-il un certificat de taille sous-exponentielle?

13

En supposant que NP! = CoNP, il n'y a pas de certificat de taille polynomiale pour un problème coNP-complet. Mais qu'en est-il du certificat de taille sous-exponentielle? En particulier pour coSAT, existe-t-il une preuve de taille sous-exponentielle pour prouver qu'une formule n'est pas satisfaisante? Sinon, quelle est la preuve négative? Merci

cc.complexity-theory proof-complexity Xi Wu
la source

cstheory.stackexchange.com/questions/22022/…

Igor Shinkar

12

C'est le sujet de la complexité de la preuve, c'est-à-dire la taille des certificats pour le problème ( ). $\mathbf{co\text{-}NP}\text{-}complete$ $TAUT$ $= coSAT$

La réponse courte est: elle est ouverte.

Du côté négatif, nous ne pouvons même pas montrer qu'il n'y a pas de réfutations de polysize pour les formules insatisfaisantes (sans parler de la question générale de le montrer pour un système de preuve arbitraire, un système de preuve propositionnelle peut être considéré comme un algorithme non déterministe pour ). $Frege$ $TAUT$

La question est également équivalente à . $\mathbf{coNP} \subseteq NTime(2^{o(n)})$

Kaveh
la source

1

Merci. Alors quelle est la croyance générale à ce problème? Je suppose que la communauté a fait une "supposition" sur le résultat.

Xi Wu

Je n'ai pas de bonne réponse et je ne me souviens pas avoir entendu de conjectures / suppositions à ce sujet, la seule chose connexe qui me vient à l'esprit en ce moment est que certains experts trouvent plausible que EF (Extended-Frege) soit une preuve optimale , mais EF étant un système de preuve optimal aurait du sens même si certains théorèmes n'ont pas de preuves EF sous-exponentielles (ie ). Il y a des chercheurs qui trouvent même plausible, et d'autres pensent 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

Une implication possible de ceci serait que du résultat de Ryan William (puisque vous auriez alors un algorithme co-non déterministe pour CircuitSAT fonctionnant en temps plus vite que exponentiel). Pas vraiment des preuves négatives, mais quand même ... $NEXP \nsubseteq P/poly$

Ramprasad
la source

Merci. J'ai tendance à interpréter votre réponse comme la difficulté de montrer que le problème coNP-complet a une preuve de taille sous-exponentielle, car alors nous avons une belle séparation.

Xi Wu

Le problème coNP-complete a-t-il un certificat de taille sous-exponentielle?

Réponses: