p ≠ np: The Set of Deterministic Problems that are Solvable in Polynomial Time is Unequal to the Set of Non-Deterministic Problems that are Solvable in Polynomial Time

Abstract

This study constructs a solution to the “p vs. np” problem using complexity theory. We show through counterexamples that p ≠ np and formalize the two sets using stochastic, probabilistic and non-deterministic modeling. While the well-known sets “pspace” and “npspace”, analyzing the storage of a device, can be claimed to be equal, p and np differ and are exclusively defined through the elapsed time of their algorithms. Indeed, calculations including the probabilistic family of discrete uniform distributions prove the well-known inequality p ≠ np. In this study, using complexity and probability theory, we give some examples that fit into the new theory: There are problems that can be solved by non-deterministic Turing machines and which are in np (they are non-deterministic and just of polynomial time growth), but they are not in p itself (since they are not, deterministic and just of polynomial time growth)