1
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ What is the PCP characterization of P ? I only know the PCP characterization of NP $\endgroup$
    – Suresh Venkat
    Commented Aug 24, 2010 at 21:32
  • 1
    $\begingroup$ A possible charctrization is PCP(0, log n) = P (from Computational Complexity: A Modern Approach by Arora and Barak), But is this optimal? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Aug 24, 2010 at 23:16
  • 9
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Aug 24, 2010 at 23:25
  • 3
    $\begingroup$ 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? $\endgroup$
    – Robin Kothari
    Commented Aug 25, 2010 at 0:30
  • 1
    $\begingroup$ 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? $\endgroup$
    – Daniel Apon
    Commented Mar 8, 2014 at 22:16

3 Answers 3

Reset to default
8
$\begingroup$

The PCP Theorem is a theorem about checking proofs, i.e. that there exist locally checkable proof systems, ones that don't "turn from non-accepting to accepting by changes that would be insignificant by any reasonable metric" (quote, top of page 2 here).

Simply stated, it's not directly related to "efficient computation" at all -- more of "efficient checking," for an appropriate definition of efficient.

I suppose it might be possible to use the machinery and terminology of PCPs to attack P vs NP, but it seems likely that such an argument would have a simpler statement under a different model and mode of thought to me. If nothing else -- I haven't seen any attempts in that direction.

Improve this answer
$\endgroup$
3
$\begingroup$

You can also find some related results in Section 10 in the paper "Free Bits, PCPs, and Nonapproximability - Towards Tight Results" by Bellare, Goldreich and Sudan.

Improve this answer
$\endgroup$
2
$\begingroup$

PCP[O(log n), 0]=P as one can deterministically simulate such a PCP in polytime by trying all possible logarithmic-length random strings. Besides, PCP[poly(n), 0]=coRP by definition, so PCP[poly(n), 0]=P assuming P=RP=coRP.

On the other hand, I don't think PCP characterizations can help us separate P and NP. While PCP certainly provide a new look at the traditional classes, it does not seem to offer a new way in which we may get around the known barriers.

Improve this answer
$\endgroup$

Your Answer

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

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