For MAXCLIQUEMAXCLIQUE problem. A constant factor polynomial-time approximation algorithm doesn’t exist unless NPDTIME(2(logn)O(1))NP\in DTIME(2^{(\log n)^{O(1)}}), based on the theorem that NPPCP((logn)O(1),(logn)O(1))NP\subseteq PCP((\log n)^{O(1)},(\log n)^{O(1)}).

Use a different approach the final PCPPCP theorem implies that a constant factor polynomial-time approximation algorithm for MAXE3SATMAXE3SAT doesn’t exist unless P=NPP=NP.

Optimization is hard \Rarr A corresponding gap version of decision problem is hard.

📖Definition 53. An NPNP-optimization problem Π\Pi is given by a polynomial pp, a language LPL\in P, a polynomial-time computable function valval called objective function, and a choice of being either a maximization problem or a minimization problem. For a given xx, define the set F(x)F(x) of feasible solution by

F(x)=\{y:|y|\le p(|x|)\and\langle x,y\rangle\in L\}.

Assume that F(x)F(x)\neq\empty for any xx. The function valval takes as input xx and yF(x)y\in F(x) and assigns a value val(x,y)0val(x,y)\ge0 to the feasible solution yy to instance xx.

Denote valx(y)val_x(y) for val(x,y)val(x,y).

  • If Π\Pi is a maximization problem, OPT(x)=maxyF(x)valx(y)OPT(x)=\max_{y\in F(x)}val_x(y).
  • If Π\Pi is a minimization problem, OPT(x)=minyF(x)valx(y)OPT(x)=min_{y\in F(x)}val_x(y).

A feasible solution yF(x)y\in F(x) s.t. valx(y)=OPT(x)val_x(y)=OPT(x) is called an optimal solution for xx.

“Gap-version” reduction: The corresponding decision problem is that of asking whether OPT(x)KOPT(x)\ge K in case of a maximization problem or whether OPT(x)KOPT(x)\le K in case of a minimization problem.

When this is NPNP-hard, it follows that there is no polynomial-time algorithm that on input xx computes an optimal solution for xx unless P=NPP=NP.

📖Definition 54. Let Π\Pi be an NPNP-optimization problem and let ρ:NR+\rho:\N\to\R_+ be a function. A ρ\rho-approximation algorithm AA is an algorithm that on input xx gives as output yF(x)y\in F(x) s.t. valx(y)ρ(x)OPT(x)val_x(y)\ge\rho(|x|)OPT(x) in case of a maximization problem Π\Pi or such that valx(y)ρ(x)OPT(x)val_x(y)\le\rho(x)OPT(x) in case of a minimization problem Π\Pi.

Let Π\Pi be an NPNP-maximization problem and let a,b:NR+a,b:\N\to\R_+ be functions s.t. 0<a(n)<b(n)0\lt a(n)\lt b(n) for all nn. Then define the following promise decision problem.

(a,b)GAPΠ(a,b)-GAP-\Pi:

  • Input: xx s.t. either OPT(x)a(x)OPT(x)\le a(|x|) or OPT(x)b(x)OPT(x)\ge b(|x|).
  • Question: Is OPT(x)b(x)OPT(x)\ge b(|x|).

📖Definition 55. We say that (a,b)GAPΠ(a,b)-GAP-\Pi is NPNP-hard if there is a polynomial-time computable function ff s.t.

  1. If xSATx\in SAT then f(x)f(x) is an instance of Π\Pi and OPT(f(x))b(f(x))OPT(f(x))\ge b(|f(x)|).
  2. If x∉SATx\not\in SAT then f(x)f(x) is an instance of Π\Pi and OPT(f(x))a(f(x))OPT(f(x))\le a(f(|x|)).

🤔Proposition 19. Suppose that (a,b)GAPΠ(a,b)-GAP-\Pi is NPNP-hard. Then there is no polynomial-time ρ\rho-approximation for Π\Pi s.t. ρ(n)>a(n)b(n)\rho(n)\gt\frac{a(n)}{b(n)} unless P=NPP=NP.

The FGLSS reduction

这真的是人能想出来的规约么

Let LPCPc,s(r(n),q(n))L\in PCP_{c,s}(r(n),q(n)) and let VV be a corresponding PCPPCP verifier.

WLOG, VV makes q(n)q(n) queries to the proof on input xx of length nn.

For an input xx, we define a graph G(x)G(x) from VV calledd the FGLSSFGLSS graph. The set of vertices G(x)G(x) are all pairs (y,z){0,1}r(n)×{0,1}q(n)(y,z)\in\{0,1\}^{r(n)}\times\{0,1\}^{q(n)}.

A pair of distinct vertices (y1,z1)(y_1,z_1) and (y2,z2)(y_2,z_2) are connected by an edge iff there exist a proof π\pi s.t. the following holds:

  1. Using y1y_1 in place of the random bits Vπ(x)V^\pi(x) accepts and the positions read from the proof π\pi contain exactly the contents of z1z_1.
  2. Using y2y_2 in place of the random bits Vπ(x)V^\pi(x) accepts and the positions read from the proof π\pi contain exactly the contents of z2z_2.

👀For a fixed input xx, the positions read from the proof are determined just by the string y{0,1}r(n)y\in\{0,1\}^{r(n)} of random bits.

Thus in the graph G(x)G(x) there are no edges between (y,z1)(y,z_1) and (y,z2)(y,z_2) for z1z2z_1\neq z_2.

A clique in G(x)G(x) must consist of vertices (y1,z1),,(yk,zk)(y_1,z_1),\cdots,(y_k,z_k) for which all the strings y1,,yky_1,\cdots,y_k are distinct.

Now define MAXCLIQUEMAXCLIQUE

Clique,中文翻译为“完全子图”。最大完全子图就是要找包含点数最多的完全子图。这个问题是 NP-complete 的。

  • Instance: A graph GG.
  • Output: Clique in GG of maximum size.

🤔Lemma 20. Let VV be a PCPPCP verifier using r(n)r(n) random bits and querying q(n)q(n) symbols from a proof π{0,1}\pi\in\{0,1\}^*. For an input xx we have

OPT(G(x))=2r(n)maxπPr[Vπ(x)=yes].OPT(G(x))=2^{r(n)}\max_\pi\Pr[V^\pi(x)=yes].

🤔Corollary 13. Let LPCPc,s(r(n),q(n))L\in PCP_{c,s}(r(n),q(n)) and let VV be a corresponding PCP verifier. Then using time 2O(r(n)+q(n))nO(1)2^{O(r(n)+q(n))}n^{O(1)} on input xx of length nn a graph G(x)G(x) with 2r(n)+q(n)2^{r(n)+q(n)} vertices can be computed s.t.

  • If xLx\in L then OPT(G(x))c2r(n)OPT(G(x))\ge c2^{r(n)}.
  • If x∉Lx\not\in L then OPT(G(x))s2r(n)OPT(G(x))\le s2^{r(n)}.

Since NPPCP(O(logn),O(1))NP\in PCP(O(\log n),O(1)), there is a δ>0\delta\gt0 s.t. (12δn,δn)GAPMAXCLIQUE(\frac{1}{2}\delta n,\delta n)-GAP-MAXCLIQUE that for MAXCLIQUEMAXCLIQUE there is no (12+ϵ)(\frac{1}{2}+\epsilon)-approximation algorithm, for any ϵ>0\epsilon\gt0, unless P=NPP=NP.

🎯Theorem 54. For any constant ρ>0\rho\gt0, there is no polynomial time ρ\rho-approximation algorithm for MAXCLIQUEMAXCLIQUE unless P=NPP=NP.

Actually, it is possible to do success amplification in a randomness efficient manner using random walks on expander graphs. This leads to NPPCP1,1/n(O(logn),O(logn))NP\subseteq PCP_{1,1/n}(O(\log n),O(\log n)) which leads to a stronger result.

🎯Theorem 55. There exist a constant ϵ>0\epsilon\gt0 s.t. there is no 1nϵ\frac{1}{n^\epsilon}-approximation algorithm for MAXCLIQUEMAXCLIQUE unless P=NPP=NP.

By using a weaker version of theorem 52 that computing FGLSSFGLSS takes 2(logn)O(1)2^{(\log n)^{O(1)}} time, we have a weaker version of theorem 54.

🎯Theorem 56 (weaker than 54). For any constant ρ>0\rho\gt0, there is no ρ\rho-approximation algorithm for MAXCLIQUEMAXCLIQUE running in time 2(logn)O(1)2^{(\log n)^{O(1)}} unless NPDTIME(2(logn)O(1))NP\neq\subseteq DTIME(2^{(\log n)^{O(1)}}).

🎯Theorem 57. For any constant ϵ>0\epsilon\gt0 there is no polynomial time 1n1ϵ\frac{1}{n^{1-\epsilon}}-approximation algorithm for MAXCLIQUEMAXCLIQUE unless P=NPP=NP.

Constraint Satisfaction Problem

📖Definition 56. A constraint satisfaction problem (CSP) is given by a finite set Σ\Sigma, an integer qq and a list of functions Φ=(φ1,φ2,,φm)\Phi=(\varphi_1,\varphi_2,\cdots,\varphi_m) where φi\varphi_i are called constraints, qq the arity, and Σ\Sigma the alphabet. An input xΣnx\in\Sigma^n satisfies the constraint φi\varphi_i if φi(x)=1\varphi_i(x)=1. Define

val(Φ)=1mmaxx{i{1,,m}φi(x)=1}.val(\Phi)=\frac{1}{m}\max_x|\{i\in\{1,\cdots,m\}|\varphi_i(x)=1\}|.

Let MAXqCSPΣMAX_qCSP_\Sigma be the optimization problem where the input is any CSP with qq-ary constraints over an alphabet Σ\Sigma.

When Σ={0,1}\Sigma=\{0,1\}, we called it MAXqCSPMAX_qCSP.

MAXE3SATMAXE3SAT problem can be phrased as CSPCSP with 3-ary constraint over the binary alphabet.

MAXE3SATMAXE3SAT:

  • Instance: CNF formula φ\varphi where each clause contains 3 distinct variables.
  • Output: Assignment xx maximizing the fraction of satisfied clauses.

The existence of an ϵ<1\epsilon\lt1 such that (ϵ,1)GAPMAXE3SAT(\epsilon,1)-GAP-MAXE3SAT is NPNP-hard.

🎯Theorem 58. For fixed s<cs\lt c we have that NPPCPc,sΣ(O(logn),q)NP\subseteq PCP_{c,s}^\Sigma(O(\log n),q) iff (s,c)GAPMAXqCSPΣ(s,c)-GAP-MAX_qCSP_\Sigma is NPNP-hard.

🎯Theorem 59. There exist ϵ<1\epsilon\lt1 s.t. (ϵ,1)GAPMAXE3SAT(\epsilon,1)-GAP-MAXE3SAT is NPNP-hard.