Том 71
№ 11

All Issues

On a criterion of $NP$-completeness

Bulitko V. K., Bulitko V. V.

Full text (.pdf)


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