Theoretical Computer Science
- cc.complexity-theory pcp proof-complexity
- Updated Tue, 21 Jun 2022 03:43:56 GMT
-
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))]$?
Solution
No results like $coNP\not\subseteq PCP[o(n),q]$ are known. Unfortunately, separating $NP$ and $coNP$ is not a low hanging fruit...
Comments (3)
- +0 – 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 07, 2010 at 02:57
- +4 – 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 08, 2010 at 05:37
- +1 – @Boaz, This is a nice answer. Could you move it and make it a separate answer? — Nov 25, 2010 at 11:32