Knapsack Pseudo Polynomial

Revision en1, by Ygor_Ribeiro, 2022-05-17 15:22:30

I have the same question which can be read through this link: https://cs.stackexchange.com/questions/111227/still-not-understanding-why-the-knapsack-problem-does-not-have-a-polynomial-time

Could someone explain to me why we don't apply the same logic to the value of n ?

I would also like to understand the complexity relationship according to the values, which in the case of the knapsack problem is O(nW) and complexity according to the input size, which in this case is O(n logW), in many forums the people talk about it and I still don't understand how the input complexity turns into the complexity of values.

Another question is about sorting methods, the complexity in relation to the values ​​is O(n^2), but the input size would be O(n * logMAX), as the largest value has no relation to the complexity of the values ​​so that's why not change nothing?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Ygor_Ribeiro 2022-05-17 15:22:30 894 Initial revision (published)