<p>I think the following paper will help:
<a href="http://dx.doi.org/10.1016/j.tcs.2007.06.013" rel="noreferrer">Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy</a></p>

<p>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.)</p>

<p>Regarding the natural relation between interactive &amp; probabilistically checkable proofs, I think the above result must help.</p>

<p>I also suggest taking a look at <a href="http://www.cs.princeton.edu/~mohammad/files/papers/SamNP.pdf" rel="noreferrer">A New Sampling Protocol and Applications to Basing Cryptogaphic Primitives on the Hardness of NP</a>.</p>

CC BY-SA 2.5
2010-09-06T20:54:03.633Z
Could you please elaborate on the relevance of the second paper?
Iddo Tzameret
CC BY-SA 2.5
2010-09-07T03:13:33.613Z
An informal introduction to the second paper is given [here](http://www.cs.cornell.edu/courses/cs7890/2010sp/MohammedMahmoody3110.htm). 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.
Sadeq Dousti
CC BY-SA 2.5
2010-09-06T17:26:04.257Z
2010-09-06T17:26:04.257Z
Sadeq Dousti
<p>No results like $coNP\not\subseteq PCP[o(n),q]$ are known.
Unfortunately, separating $NP$ and $coNP$ is not a low hanging fruit...</p>

CC BY-SA 2.5
2010-11-25T11:32:19.157Z
@Boaz, This is a nice answer. Could you move it and make it a separate answer?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-07T02:57:53.893Z
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.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-08T05:37:55.463Z
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)]$.
Boaz Barak
CC BY-SA 2.5
2010-10-07T00:24:56.660Z
2010-10-07T00:24:56.660Z
Dana Moshkovitz
<p>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$.</p>

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

CC BY-SA 2.5
2010-09-04T21:23:04.193Z
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: http://www.wisdom.weizmann.ac.il/~orm/papers/efficient_pcps_overview.pdf
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T13:43:57.187Z
You mention proof complexity in the title (and the original tags).  Is the computational complexity of the Tautology problem related to proof complexity?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T20:36:56.073Z
Yes, if P=CoNP then Tautologies would have short proofs.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-06T20:43:04.267Z
@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.
Iddo Tzameret
CC BY-SA 2.5
2010-09-06T20:44:40.240Z
@turkistany, you meant NP=coNP.
Iddo Tzameret
CC BY-SA 2.5
2010-09-06T21:02:26.397Z
@Iddo, If P=CoNP then NP=CoNP.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-06T21:12:16.913Z
@Iddo Tzameret: I see the connection.  Thanks!
Tsuyoshi Ito
<cc.complexity-theory><pcp><proof-complexity>
PCP theorem and proof complexity?
Mohammad Al-Turkistany
# PCP theorem and proof complexity?

(Asked by: username_0 on 2010-09-04)

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

**Tags:** cc.complexity-theory, pcp, proof-complexity

> **Comments:**
> **username_1**: 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: http://www.wisdom.weizmann.ac.il/~orm/papers/efficient_pcps_overview.pdf  
> **username_1**: You mention proof complexity in the title (and the original tags).  Is the computational complexity of the Tautology problem related to proof complexity?  
> **username_0**: Yes, if P=CoNP then Tautologies would have short proofs.  
> **username_2**: @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.  
> **username_2**: @turkistany, you meant NP=coNP.  
> **username_0**: @Iddo, If P=CoNP then NP=CoNP.  
> **username_1**: @username_2: I see the connection.  Thanks!  

---

## 2 answers

### Answer by username_4 on 2010-10-07. Score: 12 | Accepted answer

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

> **Comments:**
> **username_5**: 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.  
> **username_6**: 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)]$.  
> **username_0**: @Boaz, This is a nice answer. Could you move it and make it a separate answer?  

---

### Answer by username_3 on 2010-09-06. Score: 12

I think the following paper will help:
[Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy](http://dx.doi.org/10.1016/j.tcs.2007.06.013)

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](http://www.cs.princeton.edu/~mohammad/files/papers/SamNP.pdf).

> **Comments:**
> **username_2**: Could you please elaborate on the relevance of the second paper?  
> **username_3**: An informal introduction to the second paper is given [here](http://www.cs.cornell.edu/courses/cs7890/2010sp/MohammedMahmoody3110.htm). 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.  

---

