Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 27 down vote favorite
4

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?

share|improve this question

4 Answers

up vote 25 down vote accepted

This paper http://epubs.siam.org/doi/abs/10.1137/S0895480100376794 provides such an example.

Using the PCP-Theorem, Khanna, Linial, and Safra proved that it is NP-hard to color a 3-colorable graph using just 4 colors. Later, the paper pointed by the hyperlink gives, among other nice things, a PCP-free proof for the same result.

share|improve this answer
7  
Would you be willing to describe the article in your answer, rather than just pointing at it with a hyperlink? – Niel de Beaudrap Dec 2 '12 at 13:06
up vote 12 down vote

For the maximum edge disjoint paths problem in directed graphs the paper of Ma and Wang http://www.sciencedirect.com/science/article/pii/S0022000099916616 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 etal which gave improved hardness as well. http://www.sciencedirect.com/science/article/pii/S0022000003000667

share|improve this answer
But does 2-disjointpath hardness require the PCP ? – Suresh Venkat♦ Dec 2 '12 at 21:33
1  
@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. – Chandra Chekuri Dec 3 '12 at 3:04
up vote 10 down vote

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

share|improve this answer
1  
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?) – Daniel Apon Dec 2 '12 at 15:36
2  
@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. – Colin McQuillan Dec 4 '12 at 2:43
up vote 5 down vote

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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