# 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 Commented Aug 24, 2010 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? Commented Aug 24, 2010 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. Commented Aug 24, 2010 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? Commented Aug 25, 2010 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? Commented Mar 8, 2014 at 22:16