11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Nov 12, 2012 at 17:09

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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:

$\endgroup$
2
$\begingroup$

(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)

$\endgroup$
2
  • 2
    $\begingroup$ 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) $\endgroup$
    – SamM
    Nov 12, 2012 at 20:17
  • 5
    $\begingroup$ Well, NP = coNP implies $\mathrm{coNP}\subseteq\mathrm{NP}/\mathrm{poly}$, which in turn implies $\Sigma^P_3=\Pi^P_3$. $\endgroup$ Nov 13, 2012 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.