<p>NP is equal to coNP if and only if there are efficiently verifiable proofs of unsatisfiability. I.e., if and only if there exists a polynomial time turing machine $M$, which given any SAT formula $\phi$ and a string $\pi$ outputs $M(\phi, \pi) = 1$ if and only if $\phi$ is unsatisfiable. Most theorists believe there are no such efficient proofs, but proving that they don't exist would resolve the P vs NP question. However, there has been progress in showing that proofs of a restricted type must necessarily be superpolynomial in size. This is the subject of proof complexity: see the <a href="http://www.cs.toronto.edu/~sacook/homepage/cook_reckhow.pdf">foundational paper</a> by Cook and Reckhow, the  <a href="http://www.karlin.mff.cuni.cz/~krajicek/ecm.pdf">survey</a> by Krajicek, or these <a href="http://people.cs.uchicago.edu/~razborov/teaching/winter09/notes.pdf">lecture notes</a> by Razborov.</p>

CC BY-SA 3.0
2012-11-12T17:43:19.387Z
2012-11-12T17:43:19.387Z
Sasho Nikolov
<p>As implied by @Sasho's answer, you will have more luck if you search for the equivalent question of "existence of a super propositional proof system" than directly for "$\mathsf{NP}$ vs. $\mathsf{coNP}$". It is the central question of propositional proof complexity. A large portion of the area has been on proving super-polynomial lower-bounds for particular proof systems (in classical complexity theory terms, proving that some particular non-deterministic algorithms cannot solve $\mathsf{coNP}$ problems in polynomial time).</p>

<p>Sam Buss has a nice recent article which is readable by general-audience. You may want to check it:</p>

<ul>
<li>Samuel Buss, "<a href="http://www.math.ucsd.edu/~sbuss/ResearchWeb/lfcsSurvey/" rel="nofollow">Towards NP-P via Proof Complexity and Search</a>", APAL, 2012.</li>
</ul>

CC BY-SA 3.0
2012-11-12T19:08:51.237Z
2012-11-12T23:06:51.663Z
2012-11-12T23:06:51.663Z
Kaveh
<p>(it is not always pointed out that <a href="http://en.wikipedia.org/wiki/CoNP" rel="nofollow">coNP</a> $\neq$ NP $\rightarrow$ P $\neq$ NP; this is because P is closed under complementation. dont see even Wikipedia currently stating that clearly.)
have not heard of even an older survey that focuses on the NP $\stackrel{?}{=}$ coNP question in particular, it may be that its perceived as presumably tightly coupled to, or "at least as hard" as P $\stackrel{?}{=}$ NP. the subj is touched on in some P vs NP surveys, &amp; eg some mention of coNP in Allender 2009 [2]. as for recent nearby/related results try [1]:</p>

<p>[1] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.4503" rel="nofollow">NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly </a> by Harry Buhrman, John M. Hitchcock 
 (2008)  </p>

<p>[2] <a href="http://ftp.cs.rutgers.edu/pub/allender/advances.in.computing.pdf" rel="nofollow">A status report on the P vs NP question</a> Allender (2009)  </p>

CC BY-SA 3.0
2012-11-12T20:17:58.227Z
What is the relationship between coNP $\subseteq$ NP/poly and NP = coNP?

(I'm not asking rhetorically; it seems to me that the questions are very different but there may be something I'm not aware of)
SamM
CC BY-SA 3.0
2012-11-13T12:17:27.773Z
Well, NP = coNP implies $\mathrm{coNP}\subseteq\mathrm{NP}/\mathrm{poly}$, which in turn implies $\Sigma^P_3=\Pi^P_3$.
Emil Jeřábek
CC BY-SA 3.0
2012-11-12T17:03:36.800Z
2012-11-12T17:20:43.987Z
2012-11-12T17:20:43.987Z
vzn
<p>I am interested in the question of whether NP is equal to coNP or not. I'd much appreciate some advice on good publications to read on the topic.</p>

<p>For the record, I know that this question is intimately connected to the question of whether P equals NP or not (such that if NP != coNP then P != NP).</p>

<p>Cheers,
Derek</p>

CC BY-SA 3.0
2012-11-12T17:09:48.233Z
note some good P =? NP surveys will cover this. Fortnows ACM survey 2009 does not mention coNP but Allender 2009 does have some brief references.
vzn
<cc.complexity-theory><reference-request><p-vs-np>
Recent publications on NP ?= coNP question
djkern
# Recent publications on NP ?= coNP question

(Asked by: username_0 on 2012-11-11)

I am interested in the question of whether NP is equal to coNP or not. I'd much appreciate some advice on good publications to read on the topic.

For the record, I know that this question is intimately connected to the question of whether P equals NP or not (such that if NP != coNP then P != NP).

Cheers,
Derek

**Tags:** cc.complexity-theory, reference-request, p-vs-np

> **Comments:**
> **username_1**: note some good P =? NP surveys will cover this. Fortnows ACM survey 2009 does not mention coNP but Allender 2009 does have some brief references.  

---

## 3 answers

### Answer by username_2 on 2012-11-12. Score: 10

NP is equal to coNP if and only if there are efficiently verifiable proofs of unsatisfiability. I.e., if and only if there exists a polynomial time turing machine $M$, which given any SAT formula $\phi$ and a string $\pi$ outputs $M(\phi, \pi) = 1$ if and only if $\phi$ is unsatisfiable. Most theorists believe there are no such efficient proofs, but proving that they don't exist would resolve the P vs NP question. However, there has been progress in showing that proofs of a restricted type must necessarily be superpolynomial in size. This is the subject of proof complexity: see the [foundational paper](http://www.cs.toronto.edu/~sacook/homepage/cook_reckhow.pdf) by Cook and Reckhow, the [survey](http://www.karlin.mff.cuni.cz/~krajicek/ecm.pdf) by Krajicek, or these [lecture notes](http://people.cs.uchicago.edu/~razborov/teaching/winter09/notes.pdf) by Razborov.


---

### Answer by username_3 on 2012-11-12. Score: 7

As implied by @Sasho's answer, you will have more luck if you search for the equivalent question of "existence of a super propositional proof system" than directly for "$\mathsf{NP}$ vs. $\mathsf{coNP}$". It is the central question of propositional proof complexity. A large portion of the area has been on proving super-polynomial lower-bounds for particular proof systems (in classical complexity theory terms, proving that some particular non-deterministic algorithms cannot solve $\mathsf{coNP}$ problems in polynomial time).

Sam Buss has a nice recent article which is readable by general-audience. You may want to check it:

* Samuel Buss, "[Towards NP-P via Proof Complexity and Search](http://www.math.ucsd.edu/~sbuss/ResearchWeb/lfcsSurvey/)", APAL, 2012.


---

### Answer by username_1 on 2012-11-12. Score: 2

(it is not always pointed out that [coNP](http://en.wikipedia.org/wiki/CoNP) $\neq$ NP $\rightarrow$ P $\neq$ NP; this is because P is closed under complementation. dont see even Wikipedia currently stating that clearly.)
have not heard of even an older survey that focuses on the NP $\stackrel{?}{=}$ coNP question in particular, it may be that its perceived as presumably tightly coupled to, or "at least as hard" as P $\stackrel{?}{=}$ NP. the subj is touched on in some P vs NP surveys, & eg some mention of coNP in Allender 2009 [2]. as for recent nearby/related results try [1]:

[1] [NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.4503)  by Harry Buhrman, John M. Hitchcock
(2008)

[2] [A status report on the P vs NP question](http://ftp.cs.rutgers.edu/pub/allender/advances.in.computing.pdf) Allender (2009)

> **Comments:**
> **username_4**: What is the relationship between coNP $\subseteq$ NP/poly and NP = coNP?  (I'm not asking rhetorically; it seems to me that the questions are very different but there may be something I'm not aware of)  
> **username_5**: Well, NP = coNP implies $\mathrm{coNP}\subseteq\mathrm{NP}/\mathrm{poly}$, which in turn implies $\Sigma^P_3=\Pi^P_3$.  

---

