2019
Том 71
№ 11

All Issues

On a criterion of $NP$-completeness

Bulitko V. K., Bulitko V. V.

Full text (.pdf)


Abstract

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.

English version (Springer): Ukrainian Mathematical Journal 50 (1998), no. 12, pp 1924-1928.

Citation Example: Bulitko V. K., Bulitko V. V. On a criterion of $NP$-completeness // Ukr. Mat. Zh. - 1998. - 50, № 12. - pp. 1686–1691.

Full text