On a criterion of NP-completeness

被引：0

作者：

Bulitko V.K. ^{[1
]}

Bulitko V.V. ^{[1
]}

机构：

[1] Odessa University, Odessa

来源：

Ukrainian Mathematical Journal | 1998年 / 50卷 / 12期

关键词：

Recursive Function; Computable Enumeration; Mass Problem; Algorithmic Language; Associate Polynomial;

D O I：

10.1007/BF02514208

中图分类号：

学科分类号：

摘要：

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. © 1999 Kluwer Academic/Plenum Publishers.

引用

页码：1924 / 1928