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

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

2 Answers 2

Reset to default
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...

Improve this answer
$\endgroup$
3
  • $\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, 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$
    – Mohammad Al-Turkistany
    Nov 25, 2010 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you please elaborate on the relevance of the second paper? $\endgroup$
    – Iddo Tzameret
    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$
    – Sadeq Dousti
    Sep 7, 2010 at 3:13

Your Answer

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

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