Recent Advances in Mathematical Research and Computer Science Vol. 4

Abstract

In this paper is shown that the classes P and NP do not coincide, by constructing a relatively simple example of unsolvability in polynomial time in a particular well-known NP-complete problem. For a particular NP-complete problem, a random process is constructed that generates solution with random numbers. Here will be shown that the assumption that a concrete NP-complete problem belongs to the P class will contradict the random and independent choice of a concrete solution to the problem. Such a solution cannot be found with a polynomial algorithm but it can be verified with one if known. In this way, the impossibility of equality P = NP is shown.