PNP[O(LOG N)] AND SPARSE TURING-COMPLETE SETS FOR NP

被引：48

作者：

KADIN, J ^{[1
]}

机构：

[1] CORNELL UNIV,DEPT COMP SCI,ITHACA,NY 14853

来源：

关键词：

D O I：

10.1016/0022-0000(89)90024-X

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：282 / 298

页数：17

共 27 条

[1]

BEIGEL R, 1988, IN PRESS THEORET COM

[2]

Berman L., 1977, SIAM Journal on Computing, V6, P305, DOI 10.1137/0206023

[3] ON THE UNIQUE SATISFIABILITY PROBLEM [J].

BLASS, A ;

GUREVICH, Y .

INFORMATION AND CONTROL, 1982, 55 (1-3) :80-88

[4]

BUSS S, 1988, 3RD P STRUCT COMPL T, P224

[5]

CAI J, 1988, SIAM J COMPUT, V17

[6]

CHANG R, 1988, COMMUNICATION

[7] ON RELATIVIZED EXPONENTIAL AND PROBABILISTIC COMPLEXITY CLASSES [J].

HELLER, H .

INFORMATION AND CONTROL, 1986, 71 (03) :231-243

[8]

HEMACHANDRA L, 1987, 19TH P ANN ACM S THE, P110

[9]

HEMACHANDRA LA, 1986, TR86795 CORN DEP COM

[10]

Hopcroft JE., 2001, INTRO AUTOMATA THEOR, V2nd