Categories
Uncategorised

On P != NP and Matters of Chance

0-1 Knapsack Prolem is hard to solve, because the solution relies on chance.


Problem 1 (P1)

The representations Wi and Vi is assigned arbitrarily, meaning there is no relation in between Wi and Vi that we can validate a subset that satisfies given conditions without going to Index(Names) set. Since the representation functions Wi and Vi originates in separate sets, a computer has to rely on chance getting the same i values for Vi and Wi in its guesses. The way computer handles Vi and Wi seperately can be optimised, using sorting algorithms or dynamic programming. Value and Weight sets may present inner relations that such optimising are possible, but given the problem, there is no way defined for optimising the validation of the subset until a correct answer is found. This is chance.

Problem 2 (P2) – 0-1 Knapsack Problem when there is a function in between Weight and Value

If there is a function defined from Weight to Value, then our initial problem is no more and we are greeted with a new one. For the sake of simplicity, let’s assume F(w) is just a simple math operation (y = 90 + 6.5x – 0.4x^2 + 0.005*x^3) that can be done in O(1).
Now, without relying on chance of getting the guessing the indicies computer can exploit F(W) to make an educated guess about the names of the indices. This way, the problem can solved in one guess of indices.

If a computer has to play a guessing game of correct indices for a given problem class, that problem is for sure NP. If the solution can be validated in P, then it is NP-Complete. If the solution can be found with one guess, then it is in P.

Anythin beyond this point, I don’t care.
My stance regarding this issue is NP!=P.

Leave a Reply

Your email address will not be published. Required fields are marked *