Questions tagged [pcp]
Probabilistically checkable proofs
9 questions
65
votes
11
answers
5k
views
What are good references to understanding the proof of the PCP theorem?
I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}...
- 1,459
20
votes
2
answers
1k
views
Super-polynomial time approximation algorithms for MAX 3SAT
The PCP theorem states that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.
There is a ...
- 21.1k
37
votes
4
answers
4k
views
Hardness of approximation without the PCP theorem
An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any ...
- 11.4k
12
votes
3
answers
540
views
Hard gaps in maximum constraint satisfaction problems?
An equivalent formulation of PCP theorem is: For Max 3-SAT it is $NP$-hard to distinguish between satisfiable formulas and formulas where at most $r$-fraction of the clauses are satisfiable (for some $...
- 21.1k
11
votes
1
answer
709
views
PCP Theorem - Alphabet Reduction Step
What follows might seem stupid (and that probably reflects my poor understanding - so please bear with me)
I had a query on PCP theorem. We know that after the first three steps viz. Degree Reduction,...
- 1,983
7
votes
1
answer
228
views
Can NP-hard statements be proved by PCPs that only involve reading 2 bits?
For non-negative integers q, let PCP(q) denote the set of promise problems
that have polynomial-length probabalistically checkable proofs
over the binary alphabet in which the verifier only reads q ...
user6973
6
votes
2
answers
465
views
PCPs with imperfect completeness
The traditional definition of PCPs have perfect completeness -- If $x\in L$, then the prover can give a proof on which the verifier (on reading constantly many bits) always accepts. Suppose we modify ...
- 2,492
3
votes
1
answer
416
views
Consequences of Unique Games being a NPI problem
Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so UGC is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation ...
- 47
1
vote
3
answers
1k
views
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 ...
- 21.1k