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.
This is a preview of subscription content, log in via an institution to check access.
References
H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
M. R. Garey and D. S. Jonson, Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979).
L. Stockmeyer, “Classifying the computational complexity of problems,” J. Symb. Logic, 52, No. 1, 1–43 (1987).
A. Cobham, “The intrinsic computational difficulty of functions,” in: Proceedings of the Internat. Cong. on Logic Methodology and Phil. Sci., North-Holland (1964), pp. 24–30.
H. Yamada, “Real-time computation and the recursive functions not real-time computable,” IRE Trans. El. Comp., EC-11, 753–760 (1962).
Author information
Authors and Affiliations
Additional information
Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1686–1691, December, 1998.
This work was partially supported by the International Soros Program of Educational Support in Exact Sciences (grant No. GSU051239).
Rights and permissions
About this article
Cite this article
Bulitko, V.K., Bulitko, V.V. On a criterion of NP-completeness. Ukr Math J 50, 1924–1928 (1998). https://doi.org/10.1007/BF02514208
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02514208