On Correlation of Р And NP Classes
Автор: Listrovoy Sergey Vladimirovich
Журнал: International Journal of Modern Education and Computer Science (IJMECS) @ijmecs
Статья в выпуске: 3 vol.4, 2012 года.
Бесплатный доступ
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.
Theory to difficulties algorithm, Digital Systems.
Короткий адрес: https://sciup.org/15010684
IDR: 15010684
Список литературы On Correlation of Р And NP Classes
- Gary М., Johnson D. Computing machines and hard problems. – М: Mir, 1982. – 336 p.
- Cook S.А. Complexity of procedures of a conclusion of theorems. - Cybernetic collection of a new series, vol.12. - Moscow.: Mir, 1975.-P 5 - 15.
- Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freman, 1979.
- Karp R.М. Reducibility of combinational problems. - Cybernetic collection of a new series, vol. 12. - Moscow: Mir, 1975.-P16-38.
- 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.
- 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.
- Listrovoy S.V. «About polynomial reducibility in class NP» Ukrainian Mathematical Congress −2009, Algebra and Number Theory. http://www.imath.kiev.ua/
Статья научная
