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
相关论文
共 50 条
  • [1] NP-COMPLETENESS
    SCHNEIER, B
    DR DOBBS JOURNAL, 1994, 19 (10): : 119 - 121
  • [2] The NP-Completeness Column
    Johnson, David S.
    ACM TRANSACTIONS ON ALGORITHMS, 2005, 1 (01) : 160 - 176
  • [3] CONTRACTIBILITY AND NP-COMPLETENESS
    BROUWER, AE
    VELDMAN, HJ
    JOURNAL OF GRAPH THEORY, 1987, 11 (01) : 71 - 79
  • [4] NP-completeness: A retrospective
    Papadimitriou, CH
    AUTOMATA, LANGUAGES AND PROGRAMMING, 1997, 1256 : 2 - 6
  • [5] Separation of NP-completeness notions
    Pavan, A
    Selman, AL
    SIAM JOURNAL ON COMPUTING, 2002, 31 (03) : 906 - 918
  • [6] Brick wall: NP-completeness
    Franco, John
    IEEE Potentials, 1997, 16 (04): : 37 - 40
  • [7] SUBPROBLEMS AND NP-COMPLETENESS THEORY
    Su, Li Sek
    BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE, 2006, (90): : 192 - 198
  • [8] Separation of NP-completeness notions
    Pavan, A
    Selman, AL
    16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2000, : 78 - 89
  • [9] NP-completeness of kSAT and multifractals
    Sato, Y
    Taiji, M
    Ikegami, T
    COMPUTER PHYSICS COMMUNICATIONS, 1999, 121 : 51 - 53
  • [10] On NP-completeness for linear machines
    Gassner, C
    JOURNAL OF COMPLEXITY, 1997, 13 (02) : 259 - 271
12345