8
$\begingroup$

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

$\endgroup$
  • 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$ – Tsuyoshi Ito Sep 4 '10 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$ – Tsuyoshi Ito Sep 6 '10 at 13:43
  • $\begingroup$ Yes, if P=CoNP then Tautologies would have short proofs. $\endgroup$ – Mohammad Al-Turkistany Sep 6 '10 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$ – Iddo Tzameret Sep 6 '10 at 20:43
  • $\begingroup$ @turkistany, you meant NP=coNP. $\endgroup$ – Iddo Tzameret Sep 6 '10 at 20:44
12
$\begingroup$

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

$\endgroup$
  • $\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$ – Joe Fitzsimons Oct 7 '10 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 '10 at 5:37
  • 1
    $\begingroup$ @Boaz, This is a nice answer. Could you move it and make it a separate answer? $\endgroup$ – Mohammad Al-Turkistany Nov 25 '10 at 11:32
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you please elaborate on the relevance of the second paper? $\endgroup$ – Iddo Tzameret Sep 6 '10 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$ – M.S. Dousti Sep 7 '10 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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