算法和计算复杂度 12 PCP-based Inapproximability
For problem. A constant factor polynomial-time approximation algorithm doesn’t exist unless , based on the theorem that .
Use a different approach the final theorem implies that a constant factor polynomial-time approximation algorithm for doesn’t exist unless .
Optimization is hard A corresponding gap version of decision problem is hard.
📖Definition 53. An -optimization problem is given by a polynomial , a language , a polynomial-time computable function called objective function, and a choice of being either a maximization problem or a minimization problem. For a given , define the set of feasible solution by
F(x)=\{y:|y|\le p(|x|)\and\langle x,y\rangle\in L\}.
Assume that for any . The function takes as input and and assigns a value to the feasible solution to instance .
Denote for .
- If is a maximization problem, .
- If is a minimization problem, .
A feasible solution s.t. is called an optimal solution for .
“Gap-version” reduction: The corresponding decision problem is that of asking whether in case of a maximization problem or whether in case of a minimization problem.
When this is -hard, it follows that there is no polynomial-time algorithm that on input computes an optimal solution for unless .
📖Definition 54. Let be an -optimization problem and let be a function. A -approximation algorithm is an algorithm that on input gives as output s.t. in case of a maximization problem or such that in case of a minimization problem .
Let be an -maximization problem and let be functions s.t. for all . Then define the following promise decision problem.
:
- Input: s.t. either or .
- Question: Is .
📖Definition 55. We say that is -hard if there is a polynomial-time computable function s.t.
- If then is an instance of and .
- If then is an instance of and .
🤔Proposition 19. Suppose that is -hard. Then there is no polynomial-time -approximation for s.t. unless .
The FGLSS reduction
这真的是人能想出来的规约么
Let and let be a corresponding verifier.
WLOG, makes queries to the proof on input of length .
For an input , we define a graph from calledd the graph. The set of vertices are all pairs .
A pair of distinct vertices and are connected by an edge iff there exist a proof s.t. the following holds:
- Using in place of the random bits accepts and the positions read from the proof contain exactly the contents of .
- Using in place of the random bits accepts and the positions read from the proof contain exactly the contents of .
👀For a fixed input , the positions read from the proof are determined just by the string of random bits.
Thus in the graph there are no edges between and for .
A clique in must consist of vertices for which all the strings are distinct.
Now define
Clique,中文翻译为“完全子图”。最大完全子图就是要找包含点数最多的完全子图。这个问题是 NP-complete 的。
- Instance: A graph .
- Output: Clique in of maximum size.
🤔Lemma 20. Let be a verifier using random bits and querying symbols from a proof . For an input we have
🤔Corollary 13. Let and let be a corresponding PCP verifier. Then using time on input of length a graph with vertices can be computed s.t.
- If then .
- If then .
Since , there is a s.t. that for there is no -approximation algorithm, for any , unless .
🎯Theorem 54. For any constant , there is no polynomial time -approximation algorithm for unless .
Actually, it is possible to do success amplification in a randomness efficient manner using random walks on expander graphs. This leads to which leads to a stronger result.
🎯Theorem 55. There exist a constant s.t. there is no -approximation algorithm for unless .
By using a weaker version of theorem 52 that computing takes time, we have a weaker version of theorem 54.
🎯Theorem 56 (weaker than 54). For any constant , there is no -approximation algorithm for running in time unless .
🎯Theorem 57. For any constant there is no polynomial time -approximation algorithm for unless .
Constraint Satisfaction Problem
📖Definition 56. A constraint satisfaction problem (CSP) is given by a finite set , an integer and a list of functions where are called constraints, the arity, and the alphabet. An input satisfies the constraint if . Define
Let be the optimization problem where the input is any CSP with -ary constraints over an alphabet .
When , we called it .
problem can be phrased as with 3-ary constraint over the binary alphabet.
:
- Instance: CNF formula where each clause contains 3 distinct variables.
- Output: Assignment maximizing the fraction of satisfied clauses.
The existence of an such that is -hard.
🎯Theorem 58. For fixed we have that iff is -hard.
🎯Theorem 59. There exist s.t. is -hard.