-1
$\begingroup$

It is an open question if NP $\neq$ Co-NP but if the conjecture were proved, this would mean that P $\neq$ NP because P is closed under complement. Now a fact that fails to enter my head is the following:

We take 3SAT which we know is NP-complete and then we take 3TAUTOLOGY which is Co-NP-complete. The last formal language is a subset of the first, however it seems to have certain structural properties that make it (more) difficult to recognize. it is known that the certificate for SAT consists in a binary distribution of the literals that satisfies the formula but the certificate for a TAUTOLOGY must necessarily contain ALL the distributions of the variables, which must ALL satisfy the formula, otherwise we could not ascertain in any way that it is a tautology.

Therefore, based on this fact, verifying belonging to the 3SAT set by having a certificate requires time polynomial to the input but verifying membership in the set 3TAUTOLOGY no. Why is this fact not enough to show that NP $\neq$ Co-NP?

Is the reasoning correct up to this point? if so, should it still be formally demonstrated? Is it in doing this that lies the immense difficulty?

$\endgroup$
1
  • 1
    $\begingroup$ "the certificate for a TAUTOLOGY must necessarily c̶o̶n̶t̶a̶i̶n̶ cover ALL the distributions of the variables, which must ALL satisfy the formula". => We're not 100% sure this can't be done in polynomial space and time. $\endgroup$ Sep 23, 2019 at 17:29

2 Answers 2

-1
$\begingroup$

Suppose $P=NP$ then there is polynomial certificate for TAUTOLOGY and it is still open. In the world $P \neq NP$ there is still a hope for $NP = coNP$ but unlikely. May be there exits a polynomial certificate for TAUTOLOGY that shows $NP = coNP$. you can see the proof of $NL = coNL$ by Immerman or Szelepcsenyi, it is like p and np but for space complexity. before they introducing the proof many of people thought that $NL \neq coNL$.

$\endgroup$
-1
$\begingroup$

it is known that the certificate for SAT consists in a binary distribution of the literals that satisfies the formula but the certificate for a TAUTOLOGY must necessarily contain ALL the distributions of the variables, which must ALL satisfy the formula, otherwise we could not ascertain in any way that it is a tautology.

...

Is the reasoning correct up to this point? if so, should it still be formally demonstrated? Is it in doing this that lies the immense difficulty?

The error occurs when you say that a certificate for TAUTOLOGY must necessarily contain all assignments to the variables. If you can prove this, then yes, $\mathsf{NP} \neq \mathsf{coNP}$. Intuitively this may (or may not, depending on your own intuition) seem to be the case, but it is exceptionally difficult to prove.

One thing worth noting is that 2SAT is solvable in deterministic polynomial time, so your corresponding problem of 2TAUTOLOGY is also solvable in polynomial time. Accordingly, for a width-2 DNF $\varphi$, if $\varphi$ is a tautology, there is a very short certificate of this fact (and this certificate does not need to look at all possible assignments of the input variables to $\varphi$).

$\endgroup$

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.