International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 4, No. 3, 8 Mar. 2012
Cover page and Table of Contents: PDF (size: 299KB)
Author(s)
Index Terms
Theory to difficulties algorithm, Digital Systems
Abstract
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
Reference
[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/