ON CIRCUIT-SIZE COMPLEXITY AND THE LOW HIERARCHY IN NP

被引：46

作者：

KO, KI

SCHONING, U

机构：

[1] UNIV STUTTGART,INST INFORMAT,D-7000 STUTTGART 1,FED REP GER

[2] UNIV CALIF SANTA BARBARA,DEPT MATH,SANTA BARBARA,CA 93106

来源：

关键词：

D O I：

10.1137/0214003

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：41 / 51

页数：11

共 21 条

[1]

Adleman L., 1978, 19th Annual Symposium on Foundations of Computer Science, P75, DOI 10.1109/SFCS.1978.37

[2]

Bennison V. L., 1978, Theoretical Computer Science, V6, P233, DOI 10.1016/0304-3975(78)90007-5

[3]

BENNISON VL, 1978, LECTURE NOTES COMPUT, V67, P58

[4]

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

[5]

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

[6] TALLY LANGUAGES AND COMPLEXITY CLASSES [J].

BOOK, RV .

INFORMATION AND CONTROL, 1974, 26 (02) :186-193

[7] SPARSE COMPLETE SETS [J].

FORTUNE, S .

[8]

HARTMANIS J, 1983, 15TH P ACM S THEOR C, P382

[9]

KARP R, 1980, 12TH P ACM S THEOR C, P302

[10] ON SELF-REDUCIBILITY AND WEAK P-SELECTIVITY [J].

KO, KI .