IJPAM: Volume 94, No. 1 (2014)

A SHORT PROOF THAT $NP$ IS NOT $P$

Viktor Ivanov
831 Grove St. N., Saint Petersburg
FL 33701-2213, USA


Abstract. This proof of $NP\neq P$ is based on better estimates of lower bounds on the time complexity that hold for all solution algorithms. Almost no special knowledge other than logical and combinatorial efforts is needed to understand the proof.

Received: April 3, 2014

AMS Subject Classification: 03D10, 03D15, 03D9

Key Words and Phrases: algorithm time complexity, information-based complexity, problem $NP$-complete, $P$-problem, turing machine

Download paper from here.



DOI: 10.12732/ijpam.v94i1.9 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2014
Volume: 94
Issue: 1
Pages: 81 - 88

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).