<p>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:
<a href="http://www.dcs.ed.ac.uk/home/mrj/papers/DFJ02.pdf">http://www.dcs.ed.ac.uk/home/mrj/papers/DFJ02.pdf</a>
Later, Sly proved a hardness result for approximately counting independent sets just based on standard NP-hardness of Max-Cut:
<a href="http://arxiv.org/pdf/1005.5584v1.pdf">http://arxiv.org/pdf/1005.5584v1.pdf</a></p>

CC BY-SA 3.0
2012-12-02T15:36:44.303Z
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
CC BY-SA 3.0
2012-12-04T02:43:03.147Z
@DanielApon: a later result used inapproximability of MAX-CUT to give an even stronger inapproximability result: http://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
CC BY-SA 3.0
2012-12-02T15:31:45.880Z
2012-12-02T15:31:45.880Z
Dana Moshkovitz
<p>For the maximum edge disjoint paths problem in directed graphs the paper of <a href="http://www.sciencedirect.com/science/article/pii/S0022000099916616" rel="nofollow">Ma &amp; Wang (2000)</a> 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 <a href="http://www.sciencedirect.com/science/article/pii/S0022000003000667" rel="nofollow">Guruswami et. al. (2003)</a> which gave improved hardness as well.</p>

CC BY-SA 3.0
2012-12-02T21:33:07.677Z
But does 2-disjointpath hardness require the PCP ?
Suresh Venkat
CC BY-SA 3.0
2012-12-03T03:04:32.940Z
@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
CC BY-SA 3.0
2012-12-02T14:24:16.493Z
2014-03-14T03:16:56.557Z
2014-03-14T03:16:56.557Z
Chandra Chekuri
<p>Another answer, which is in a somewhat different spirit than the previous answers, is this paper of Uri Feige:
<a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=3&amp;ved=0CD8QFjAC&amp;url=http://www.wisdom.weizmann.ac.il/~feige/Approx/r3sat.ps&amp;ei=nCq9UJ2QHunkyQHq0YCQDw&amp;usg=AFQjCNEl2WfbgVob8pfzjYEgQYr-dIQxyw&amp;sig2=j_mRu8HLciPsUEw05DRs_g&amp;cad=rja">Relations between Average Case Complexity and Approximation Complexity</a>.</p>

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

CC BY-SA 3.0
2012-12-03T22:52:44.127Z
2012-12-03T22:52:44.127Z
Dana Moshkovitz
<p>An example is this paper:</p>

<p>Guruswami, V., &amp; Khanna, S. (2004). On the hardness of 4-coloring a 3-colorable graph. <em>SIAM Journal on Discrete Mathematics</em>, 18(1): 30-40. <a href="http://epubs.siam.org/doi/abs/10.1137/S0895480100376794">link</a></p>

<p>Using the PCP-Theorem, <a href="http://link.springer.com/article/10.1007/s004930070013">Khanna, Linial, and Safra (2000)</a> proved that it is NP-hard to color a 
3-colorable graph using just 4 colors. Later, Guruswami &amp; Khanna (2004) gave, among other nice things, a PCP-free proof for the same result.</p>

CC BY-SA 3.0
2012-12-02T13:06:52.790Z
Would you be willing to describe the article in your answer, rather than just pointing at it with a hyperlink?
Niel de Beaudrap
CC BY-SA 3.0
2012-12-02T12:53:38.547Z
2014-03-14T03:15:03.367Z
2014-03-14T03:15:03.367Z
vb le
<p>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?</p>

<cc.complexity-theory><approximation-hardness><pcp>
Hardness of approximation without the PCP theorem
Andras Farago
# Hardness of approximation without the PCP theorem

(Asked by: username_0 on 2012-12-02)

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?

**Tags:** cc.complexity-theory, approximation-hardness, pcp


---

## 4 answers

### Answer by username_6 on 2012-12-02. Score: 35 | Accepted answer

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](http://epubs.siam.org/doi/abs/10.1137/S0895480100376794)

Using the PCP-Theorem, [Khanna, Linial, and Safra (2000)](http://link.springer.com/article/10.1007/s004930070013) 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.

> **Comments:**
> **username_7**: Would you be willing to describe the article in your answer, rather than just pointing at it with a hyperlink?  

---

### Answer by username_4 on 2012-12-02. Score: 15

For the maximum edge disjoint paths problem in directed graphs the paper of [Ma & Wang (2000)](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 et. al. (2003)](http://www.sciencedirect.com/science/article/pii/S0022000003000667) which gave improved hardness as well.

> **Comments:**
> **username_5**: But does 2-disjointpath hardness require the PCP ?  
> **username_4**: @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.  

---

### Answer by username_1 on 2012-12-02. Score: 13

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>

> **Comments:**
> **username_2**: 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?)  
> **username_3**: @DanielApon: a later result used inapproximability of MAX-CUT to give an even stronger inapproximability result: http://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.  

---

### Answer by username_1 on 2012-12-03. Score: 10

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](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CD8QFjAC&url=http://www.wisdom.weizmann.ac.il/~feige/Approx/r3sat.ps&ei=nCq9UJ2QHunkyQHq0YCQDw&usg=AFQjCNEl2WfbgVob8pfzjYEgQYr-dIQxyw&sig2=j_mRu8HLciPsUEw05DRs_g&cad=rja).

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


---

