patternModerate
Why we can't have FPTAS for strong NP complete problems
Viewed 0 times
whyfptascancompleteforstrongproblemshave
Problem
I understood that we can apply FPTAS to the weak NP problems like 0-1 knapsack.
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.
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.
Solution
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.
Context
StackExchange Computer Science Q#16365, answer score: 10
Revisions (0)
No revisions yet.