On Correlation of Р and NP Classes

Full Text (PDF, 299KB), PP.21-27

Views: 0 Downloads: 0


Listrovoy Sergey Vladimirovich 1,*

1. Ukrainian State Academy of Railway Transport, Kharkov, Ukraine

* Corresponding author.

DOI: https://doi.org/10.5815/ijmecs.2012.03.03

Received: 12 Nov. 2011 / Revised: 5 Dec. 2011 / Accepted: 20 Jan. 2012 / Published: 8 Mar. 2012

Index Terms

Theory to difficulties algorithm, Digital Systems


It is shown an incorrectness of introduction of a class of NP-complete problems, which reason is that Cook’s S.А. theorem on that the “satisfiability” problem is the universal NP-complete problem, is not true and, therefore, the issue on existence of at least one NP-complete problem remains open, that explains failures of attempts to estimate correlations between P and NP classes.

Cite This Paper

Listrovoy Sergey Vladimirovich, "On Correlation of Р And NP Classes", International Journal of Modern Education and Computer Science (IJMECS), vol.4, no.3, pp.21-27, 2012. DOI:10.5815/ijmecs.2012.03.03


[1]Gary М., Johnson D. Computing machines and hard problems. – М: Mir, 1982. – 336 p.
[2]Cook S.А. Complexity of procedures of a conclusion of theorems. - Cybernetic collection of a new series, vol.12. - Moscow.: Mir, 1975.-P 5 - 15.
[3]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freman, 1979.
[4]Karp R.М. Reducibility of combinational problems. - Cybernetic collection of a new series, vol. 12. - Moscow: Mir, 1975.-P16-38.
[5]S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. To appear Journal of the ACM. Preliminary version in Proceedings of the Thirty Third Annual Symposium on the Foundations of Computer Science, IEEE,1992.
[6]Listrovoy S.V., Yablochkov S.V. Problem-solving procedure for the minimum vertex covers and maximum independent sets//Electronic modeling 2003, vol.25, No.2, P. 31-40.
[7]Listrovoy S.V. «About polynomial reducibility in class NP» Ukrainian Mathematical Congress −2009, Algebra and Number Theory. http://www.imath.kiev.ua/