Proof of P = NP in the P versus NP Problem
Listed in
This article is not in any list yet, why not save it to one of your lists.Abstract
The P versus NP problem is still open which means it is still not proved or disproved up until this day. This problem has emerged from developments of mathematical logic and electronic technology in the middle of the 20th century and it is one of the most important problems in mathematics and theoretical computer science. Although the academic consensus regarding this problem is that P does not = NP, in this piece of work we have gone through a different path and try to show that P = NP does indeed hold. For this purpose, we have chosen the Knapsack problem which a NP-complete problem that is among the hardest of the NP problems which is verifiable in polynomial time. By adjusting the current most efficient solution algorithm with pseudo-polynomial time complexity for the NP-complete Knapsack problem by splitting up the whole problem into multiple, finite number of subproblems each with reduced polynomial time complexity we could improve the solution time of the whole NPC Knapsack problem and make it to be solvable in polynomial time as well. This proves P = NP in general because all NP problems including the other subclassed NP-complete problems like e.g. the Travel salesman problem could be reduced resp. transformed to the one NP-complete problem that is the Knapsack problem for which we have discovered a solution algorithm in polynomial time.