# PCP characterization of NP

The PCP theorem (NP= PCP(log n, O(1)) )is a major result in complexity theory with many applications such as proving hardness of approximate results. However, it seems to me that it does not offer any insight that leads to separating P from NP or NP from coNP. My intuition is that P=NP would imply that coNP = PCP( log n, O(1)). That means Tautology instance has a proof that can be verified by an efficient probabilistic verifier using logarithmic random bits and reading only constant number of bits from a proposed proof. It seems that PCP theorem can not shed a light on why Tautology can not have such proof system.

Why is the PCP characterization of NP not helpful in separating NP from coNP ( or from P)? Is there any known barrier?

** EDIT**: Provided context and motivation.

• What is the PCP characterization of P ? I only know the PCP characterization of NP – Suresh Venkat Aug 24 '10 at 21:32
• A possible charctrization is PCP(0, log n) = P (from Computational Complexity: A Modern Approach by Arora and Barak), But is this optimal? – Mohammad Al-Turkistany Aug 24 '10 at 23:16
• I think you need to flesh this out a bit, otherwise this question is as useful (or not) as "why can't we use X characterization of P to separate it from NP". As phrased, your question appears to imply that there might be an intuitive argument for this line of attack, and if so, what is that argument ? If not, then this question isn't particularly definite or focused. – Suresh Venkat Aug 24 '10 at 23:25
• Since you mentioned that P is PCP(0, log n), I'd like to add that it is also PCP(0, 0), PCP(0, log log n), etc. How does such a characterization help separate it from NP? – Robin Kothari Aug 25 '10 at 0:30
• It seems like the recent edits have changed the content of this (originally 3.5-year old) question, to focus on NP vs coNP instead of P vs NP. (Note that the previous answers seem to no longer answer the given question..) Maybe it's better to start a new question instead? – Daniel Apon Mar 8 '14 at 22:16