SPARSE COMPLETE-SETS FOR NP - SOLUTION OF A CONJECTURE OF BERMAN AND HARTMANIS

被引：169

作者：

MAHANEY, SR ^{[1
]}

机构：

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

来源：

关键词：

D O I：

10.1016/0022-0000(82)90002-2

中图分类号：

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

学科分类号：

0812 ;

摘要：

引用

页码：130 / 143

页数：14

共 21 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[3]

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

[4]

BERMAN L, 1976, 8TH P ANN ACM S THEO, P30

[5]

BERMAN P, 1978, LECTURE NOTES COMPUT, V62, P63

BOOK, RV ;

WRATHALL, C ;

SELMAN, AL ;

DOBKIN, D .

MATHEMATICAL SYSTEMS THEORY, 1977, 11 (01) :1-8

[7] SPARSE COMPLETE SETS [J].

FORTUNE, S .

[8] COMPUTATIONAL COMPLEXITY OF PROBABILISTIC TURING MACHINES [J].

GILL, J .

[9]

HARTMANIS J, 1980, LECTURE NOTES COMPUT, V88

[10]

HARTMANIS J, 1980, TR80416 CORN U COMP