On a criterion of $NP$-completeness

• Дата: 1998
• Автори: Bulitko, V. V., Bulitko, V. K., Булитко, В. В., Булитко, В. К.
• Формат: Стаття
• Мова: Російська; Англійська
• Опубліковано: Institute of Mathematics, NAS of Ukraine 1998
• Онлайн доступ: https://umj.imath.kiev.ua/index.php/umj/article/view/4788
• Назва журналу: Ukrains’kyi Matematychnyi Zhurnal

We consider the problem of construction of criteria of completeness of sets with respect to polynomially bounded reducibilities. We present a nonstandard description of sets from the class NP, a brief proof of an analog of the well-known Cook theorem, and a criterion of NP-completeness.