It is known that if $P=NP$ then $CoNP= PCP[O(log(n)),O(1)]$. Also, it is known that $NEXP=PCP[poly(n),poly(n)]$. It appears that PCP can't tell us which natural problems are not in $NP$. I wonder if it is possible to use PCP characterization to separate $CoNP$ from $NP$.

What are the best bounds on randomness complexity $r(n)$ and query complexity $q(n)$ such that Tautology Problem is in $PCP[O(r(n)),O(q(n))]$?

  • 6
    $\begingroup$ It is known that NEXP=PCP[poly(n),O(1)] as a consequence of the PCP Theorem. See e.g. the introduction of Or Meir’s paper at FOCS 2009: wisdom.weizmann.ac.il/~orm/papers/efficient_pcps_overview.pdf $\endgroup$ Sep 4, 2010 at 21:23
  • 1
    $\begingroup$ You mention proof complexity in the title (and the original tags). Is the computational complexity of the Tautology problem related to proof complexity? $\endgroup$ Sep 6, 2010 at 13:43
  • $\begingroup$ Yes, if P=CoNP then Tautologies would have short proofs. $\endgroup$ Sep 6, 2010 at 20:36
  • $\begingroup$ @Ito, proof complexity usually studies proof systems establishing propositional tautologies. Any proof system can be thought of as a non-deterministic algorithm for the Tautology problem. Proof complexity, then, is the study of non-deterministic algorithms for the Tautology problem. $\endgroup$ Sep 6, 2010 at 20:43
  • $\begingroup$ @turkistany, you meant NP=coNP. $\endgroup$ Sep 6, 2010 at 20:44

2 Answers 2


No results like $coNP\not\subseteq PCP[o(n),q]$ are known. Unfortunately, separating $NP$ and $coNP$ is not a low hanging fruit...

  • $\begingroup$ Actually, I think that might be fortunate rather than unfortunate. If it was so simple to separate them, then the entire community would look pretty silly not to have spotted it before now. $\endgroup$ Oct 7, 2010 at 2:57
  • 4
    $\begingroup$ It's not only that such results are not known, they are probably not true. Generally, for the same reason we believe $coNP \neq NP$ we believe that non-determinism doesn't really help in solving tautologies. So, a natural assumption is that that Tautology problem cannot be solved in non deterministic time $2^{n^{o(1)}}$ (or maybe not even in time $2^{o(n)}$) which would imply that it's not in $PCP[n^{o(1)},poly(n)]$. $\endgroup$
    – Boaz Barak
    Nov 8, 2010 at 5:37
  • 1
    $\begingroup$ @Boaz, This is a nice answer. Could you move it and make it a separate answer? $\endgroup$ Nov 25, 2010 at 11:32

I think the following paper will help: Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy

It states that $\mathbf{coNP} \not\subset \mathbf{IP}[\log^{O(1)} n]$ unless the exponential hierarchy collapses. ($\mathbf{IP}[k]$ is the class of languages possessing $k$-move interactive proofs.)

Regarding the natural relation between interactive & probabilistically checkable proofs, I think the above result must help.

I also suggest taking a look at A New Sampling Protocol and Applications to Basing Cryptogaphic Primitives on the Hardness of NP.

  • $\begingroup$ Could you please elaborate on the relevance of the second paper? $\endgroup$ Sep 6, 2010 at 20:54
  • $\begingroup$ An informal introduction to the second paper is given here. The sentence "All known (even multi-prover) proof systems for co-NP require provers with #P complexity" is the heart of what relates it to the current discussion. $\endgroup$ Sep 7, 2010 at 3:13

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.