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 case where the hardness of approximation result was first proved using the PCP theorem, i.e., the result was not known before, but later a more direct proof was found that does not depend on PCP? In other words, is there any case where PCP appeared necessary first, but later it could be eliminated?
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
An example is this paper:
Guruswami, V., & Khanna, S. (2004). On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics, 18(1): 30-40. link
Using the PCP-Theorem, Khanna, Linial, and Safra (2000) proved that it is NP-hard to color a 3-colorable graph using just 4 colors. Later, Guruswami & Khanna (2004) gave, among other nice things, a PCP-free proof for the same result.
-
11$\begingroup$ Would you be willing to describe the article in your answer, rather than just pointing at it with a hyperlink? $\endgroup$ Commented Dec 2, 2012 at 13:06
$\begingroup$
$\endgroup$
2
For the maximum edge disjoint paths problem in directed graphs the paper of Ma & Wang (2000) was based on the label cover problem which in turn is based on the PCP theorem. Subsequently a simple reduction via the 2-disjointpath problem hardness was found by Guruswami et. al. (2003) which gave improved hardness as well.
-
$\begingroup$ But does 2-disjointpath hardness require the PCP ? $\endgroup$ Commented Dec 2, 2012 at 21:33
-
3$\begingroup$ @SureshVenkat, 2-disjointpaths does not require PCP. It is the problem of deciding whether there are disjoint paths connecting $(s_1,t_1)$ and $(s_2,t_2)$ in a directed graph $G$. It was shown to be NP-Complete via an intricate gadget reduction from SAT, by Fortune, Hopcroft and Wylie. $\endgroup$ Commented Dec 3, 2012 at 3:04
$\begingroup$
$\endgroup$
2
There are examples from approximate counting. Approximately counting the number of satisfying assignments of an NP-relation can only be harder than deciding whether a satisfying assignment exists, so it's not too surprising that one doesn't need the PCP theorem to prove hardness for such problems. Still, the PCP theorem sometimes gives a convenient starting point, e.g., for this paper about approximately counting the number of independent sets in a sparse graph: http://www.dcs.ed.ac.uk/home/mrj/papers/DFJ02.pdf Later, Sly proved a hardness result for approximately counting independent sets just based on standard NP-hardness of Max-Cut: http://arxiv.org/pdf/1005.5584v1.pdf
answered Dec 2, 2012 at 15:31
-
1$\begingroup$ Interesting -- does the UGC improve Sly's hardness of approximation factor here? (Edit: I guess not; he claims $d=6$ is optimal. Edit2: Unless you could rule out something stronger than PTASs? Any idea if MAX-CUT's inapproximability implies anything for partition?) $\endgroup$ Commented Dec 2, 2012 at 15:36
-
2$\begingroup$ @DanielApon: a later result used inapproximability of MAX-CUT to give an even stronger inapproximability result: arxiv.org/abs/1203.2602 shows that for some $c$ it is NP-hard to approximately count independent sets in 6-regular graphs to within ratio $e^{cn}$. I don't think the optimal value of $c$ has been investigated, under UGC or otherwise. $\endgroup$ Commented Dec 4, 2012 at 2:43
$\begingroup$
$\endgroup$
Another answer, which is in a somewhat different spirit than the previous answers, is this paper of Uri Feige: Relations between Average Case Complexity and Approximation Complexity.
Uri shows that average case assumptions can replace the PCP theorem for proving hardness of approximation of some problems. Note, however, that we don't know how to prove the average-case assumptions, and we have some evidence that we won't be able to prove them based on standard NP-hardness assumptions (see the papers of Feigenbaum-Fortnow, Bogdanov-Trevisan, etc).
answered Dec 3, 2012 at 22:52