# Recent publications on NP ?= coNP question

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

-
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 Nov 12 '12 at 17:09

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 by Cook and Reckhow, the survey by Krajicek, or these lecture notes by Razborov.

-

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:

-

(it is not always pointed out that 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 by Harry Buhrman, John M. Hitchcock (2008)

[2] A status report on the P vs NP question Allender (2009)

-
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 Nov 12 '12 at 20:17
Well, NP = coNP implies $\mathrm{coNP}\subseteq\mathrm{NP}/\mathrm{poly}$, which in turn implies $\Sigma^P_3=\Pi^P_3$. – Emil Jeřábek Nov 13 '12 at 12:17