1
$\begingroup$

In the introductory chapter of $\textbf{PCP}$ in Arora and Barak, I read the proof that why a $\textbf{PCP}(\log n, 1)$ of completeness 1 and soundness 1/2 for an $NPC$ language $L$ will imply that there exists a $\rho$ for which $\rho$-approximation algorithm for MAX-3-SAT does not exist unless $P = NP$. But in the paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf authors say that "We construct a PCP that reads two bits from the proof and accepts if and only if the two bits are unequal. The completeness and soundness are $c$ and $s$ respectively. This implies that MAX-CUT is $NP$-hard to approximate within any factor greater than $s/c$." What is the proof for this?

$\endgroup$
1
$\begingroup$

The authors give a reduction $x \mapsto f(x)$ from some NP-hard problem $X$ to MAX-CUT with the following properties:

  • If $x$ is a YES instance then $OPT(f(x)) \geq c$.
  • If $x$ is a NO instance then $OPT(f(x)) \leq s$.

Here $OPT(y)$ is the optimal value of the MAX-CUT instance $y$.

Suppose now that you had an algorithm for MAX-CUT with approximation ratio $\rho > s/c$, which means that for every instance $y$, $ALG(y) \geq \rho OPT(y)$, where $ALG(y)$ is the value of the instance produced by the algorithm. We can use this algorithm to solve $X$, since $x$ is a YES instance of $X$ iff $OPT(f(x))>s$ (I'll let you verify that).

This informally explains the statement in the paper. Any more formal explanation requires a definition of "NP-hard to approximate". One possibility is as follows. Let $Y$ be a maximization problem. We say that $Y$ is NP-hard to approximate within a factor of $\rho$ if for every problem $X \in \mathsf{NP}$ there exists a polytime computable reduction $f$ which on input $x$ produces a tuple $(y,v)$, where $y$ is an instance of $Y$ and $v$ is a number, with the following properties:

  • If $x$ is a YES instance of $X$ then $OPT(y) \geq v$.
  • If $x$ is a NO instance of $X$ then $OPT(y) < \rho v$.

This generalizes the usual definition of NP-hardness for optimization problems, which corresponds to the choice $\rho = 1$. Under this definition, if $Y$ is NP-hard to approximate within a factor of $\rho$ and there is a polytime $\rho$-approximation algorithm for $Y$, then $\mathsf{P} = \mathsf{NP}$. Finally, according to this definition, MAX-CUT is indeed NP-hard to approximate to within any factor strictly larger than $s/c$.

$\endgroup$
  • $\begingroup$ But algorithm by Goemans Williamson algorithm is a RANDOMIZED algorithm. I can see why Khot et el's result imply that there can not be better alpha-approximation algorithm than GW's constant but a randomized algorithm with better alpha can be possible? $\endgroup$ – Vimal Raj Sharma Jan 3 '18 at 5:13
  • $\begingroup$ I guess this paper answers my doubt hariharan-ramesh.com/papers/derand.pdf. The GW algorithm was derandomized in 1995. $\endgroup$ – Vimal Raj Sharma Jan 3 '18 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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