Data Structures and Algorithms

The Concept of NP-Completeness Introduces a Statistical Argument Against P=NP

Authors: Dobri Bozhilov
Comments: 5 Pages. (Note by ai.viXra.org Admin: Please cite listed scientific references)

The concept of NP-completeness summarizes a multitude of problems that can be transformed into each other through polynomial reduction. Its main idea is: "if we solve one problem in polynomial time, we will solve them all." At first glance, this is promising. But upon closer analysis, it turns out that the mechanism of reduction itself requires that each NP-complete problem has an independent polynomial-time solution. This is because the reduction represents a transition between initially necessary solutions for each separate problem, and not a means to simplify the solution by finding it in only one place. Therefore, with each new proven NP-complete problem, the necessity for a solution to exist for it is added, if such a solution is even possible. If even one does not have a solution, then none can. Thus, a statistical argument against P=NP is formed.
Category: Data Structures and Algorithms