<p>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 <a href="http://portal.acm.org/citation.cfm?id=62233">here</a>).</p>

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

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

CC BY-SA 2.5
2010-08-25T02:15:44.830Z
2010-08-25T02:15:44.830Z
Daniel Apon
<p>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.</p>

CC BY-SA 2.5
2010-08-25T03:38:45.453Z
2010-08-25T03:38:45.453Z
sangxia
<p>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.</p>

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

CC BY-SA 2.5
2010-08-25T03:33:16.200Z
2010-08-25T03:42:32.957Z
2010-08-25T03:42:32.957Z
Zeyu
<p>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.</p>

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

<p>** EDIT**: Provided context and motivation.</p>

CC BY-SA 3.0
2014-03-08T22:16:17.573Z
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
CC BY-SA 3.0
2014-03-08T23:12:27.073Z
@DanielApon Separating NP from coNP resolves the P vs NP problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-03-08T23:33:28.403Z
Also, the original post was asking two independent questions.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-24T21:32:39.210Z
What is the PCP characterization of P ? I only know the PCP characterization of NP
Suresh Venkat
CC BY-SA 2.5
2010-08-24T23:16:13.200Z
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
CC BY-SA 2.5
2010-08-24T23:25:28.117Z
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
CC BY-SA 2.5
2010-08-25T00:24:21.623Z
The idea is to try to understand what different trade-offs between the number of random bits and number of query bits could tell us about the nature of efficient computation.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-25T00:30:52.517Z
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
<cc.complexity-theory><complexity-classes><pcp>
PCP characterization of NP
Mohammad Al-Turkistany
# PCP characterization of NP

(Asked by: username_0 on 2010-08-24)

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.

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

> **Comments:**
> **username_2**: What is the PCP characterization of P ? I only know the PCP characterization of NP  
> **username_0**: A possible charctrization is PCP(0, log n) = P (from Computational Complexity: A Modern Approach by Arora and Barak), But is this optimal?  
> **username_2**: 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.  
> **username_0**: The idea is to try to understand what different trade-offs between the number of random bits and number of query bits could tell us about the nature of efficient computation.  
> **username_3**: 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?  
> **username_1**: 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?  
> **username_0**: @DanielApon Separating NP from coNP resolves the P vs NP problem.  
> **username_0**: Also, the original post was asking two independent questions.  

---

## 3 answers

### Answer by username_1 on 2010-08-25. Score: 8

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](http://portal.acm.org/citation.cfm?id=62233)).

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.


---

### Answer by username_4 on 2010-08-25. Score: 3

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.


---

### Answer by username_5 on 2010-08-25. Score: 2

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.


---

