Looking at the knapsack problem, we see it has a runtime of O(nW), where n is the length of the array of items and W is an integer representing the maximum capacity. The solution cannot be found in deterministic polynomial time, since the size of W as input is considered in bits as log W. Adding 1 to W only increases the input size when it causes us to add an extra bit. However, to solve the Knapsack we will need to run n * W operations so increasing W always increases the runtime to solve. More important is to notice the difference between input size and the order of operations to solve knapsack. The difference is not polynomial in size. The input size is n + log W while the runtime is n * W. Plot these on a graph and you’ll see the exponential difference between the input size and the growth rate for the runtime. Concerning the verifiability of knapsack, there is no known way to verify a solution in less than O(nW), so verifying also occurs in non-deterministic polynomial time.