Why we can't have FPTAS for strong NP complete problems - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-23T15:29:39Z https://cs.stackexchange.com/feeds/question/16365 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/16365 5 Why we can't have FPTAS for strong NP complete problems user2159588 https://cs.stackexchange.com/users/10944 2013-10-22T06:25:49Z 2017-11-08T23:51:21Z <p>I understood that we can apply <a href="http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme" rel="nofollow" title="fully polynomial-time approximation scheme">FPTAS</a> to the weak NP problems like 0-1 knapsack.</p> <p>But why we cant apply the same principle to the strong NP problems like bin packing? I also checked wiki page about the same but understood very less.</p> https://cs.stackexchange.com/questions/16365/-/16372#16372 1 Answer by Ron Teller for Why we can't have FPTAS for strong NP complete problems Ron Teller https://cs.stackexchange.com/users/10438 2013-10-23T19:49:18Z 2013-10-23T19:59:56Z <p>Strongly NP-Hard problems are problems for whom it had been proved that obtaining an approximation for these problems will allow us solve other NP-Complete problems.</p> <p>Here's a well-known example:</p> <p>Assume an algorithm $A$ yields an approximation $\rho$ to the TSP in polynomial time.</p> <p>Let $G$ be some graph for whom we want to determine if an Hamiltonian Circle exists (a known NP-Complete problem).</p> <p>Let $G'$ be a complete graph with the same vertices as in $G$ ($V(G) = V(G')$). Connect each two vertices in $G'$ with an edge $e=(u,v)$ with weight 0 if $e$ belong to $E(G)$, otherwise $e$ has a weight of $\rho+1$.</p> <p>Now find an approximation to the TSP on $G'$ by using $A$, if $A$ produced a solution that is $&lt; \rho+1$, we can determine that there's an Hamiltonian Path in $G$, otherwise, there isn't.</p> <p>We proved that any approximation algorithm for the TSP will allow us to solve the Hamiltionian Circle problem and thus it is strongly NP-Hard.</p> https://cs.stackexchange.com/questions/16365/-/16379#16379 6 Answer by Yuval Filmus for Why we can't have FPTAS for strong NP complete problems Yuval Filmus https://cs.stackexchange.com/users/683 2013-10-23T21:56:48Z 2013-10-23T21:56:48Z <p>If there were an FPTAS for some strongly NP-complete problems then you could use the FPTAS to solve them in polytime. Consider for example bin packing. If the solution is of order $V$, then the input size is of order $V$. Therefore a $1-1/V$-approximation can be achieved in polytime, and since the answer is an integer, such an approximation actually gives the optimal answer. I'll let you work out the details.</p>