HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Why we can't have FPTAS for strong NP complete problems

Submitted by: @import:stackexchange-cs··
0
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.

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.