PCP theorem and proof complexity?

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))]$?

• 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 Sep 4 '10 at 21:23
• You mention proof complexity in the title (and the original tags). Is the computational complexity of the Tautology problem related to proof complexity? Sep 6 '10 at 13:43
• Yes, if P=CoNP then Tautologies would have short proofs. Sep 6 '10 at 20:36
• @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. Sep 6 '10 at 20:43
• @turkistany, you meant NP=coNP. Sep 6 '10 at 20:44

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

• 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. Oct 7 '10 at 2:57
• 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)]$. Nov 8 '10 at 5:37
• @Boaz, This is a nice answer. Could you move it and make it a separate answer? Nov 25 '10 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.

• Could you please elaborate on the relevance of the second paper? Sep 6 '10 at 20:54
• 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. Sep 7 '10 at 3:13