3 ms·
Saying some problem is harder than NP Complete is like saying something is longer than "10". Without units "10" does not say anything about length. Without size
by Sankozi 3y ago
Saying some problem is harder than NP Complete is like saying something is longer than "10". Without units "10" does not say anything about length. Without size function (and basic operation set) saying some problem is EXPTIME is not telling much.
Knapsack problem is common problem that has different complexity depending on how we measure it. Just googling "knapsack problem complexity" returns two answers "O(N*W)" and "NP Hard". Both are correct depending how you specify size of the problem.