INCLUSION COMPLETE TALLY LANGUAGES AND HARTMANIS-BERMAN CONJECTURE

被引：12

作者：

BOOK, RV

WRATHALL, C

SELMAN, AL

DOBKIN, D

机构：

[1] UNIV CALIF SANTA BARBARA, DEPT MATH, SANTA BARBARA, CA 93106 USA

[2] UNIV CALIF SANTA BARBARA, PROGRAM COMP SCI, SANTA BARBARA, CA 93106 USA

[3] IOWA STATE UNIV, DEPT COMP SCI, AMES, IA 50011 USA

[4] UNIV CALIF LOS ANGELES, DEPT SYST SCI, LOS ANGELES, CA 90024 USA

[5] YALE UNIV, DEPT COMP SCI, NEW HAVEN, CT 06520 USA

来源：

MATHEMATICAL SYSTEMS THEORY | 1977年 / 11卷 / 01期

关键词：

D O I：

10.1007/BF01768464

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：1 / 8

页数：8

共 13 条

[1]

Book R. V., 1976, Theoretical Computer Science, V1, P215, DOI 10.1016/0304-3975(76)90057-8

[2] COMPARING COMPLEXITY CLASSES [J].

BOOK, RV .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (02) :213-229

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

BOOK, RV .

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

[4] CHARACTERIZATIONS OF PUSHDOWN MACHINES IN TERMS OF TIME-BOUNDED COMPUTERS [J].

COOK, SA .

JOURNAL OF THE ACM, 1971, 18 (01) :4-&

[5]

HARTMANIS J, 1976, 8TH P ACM S THEOR CO, P30

[6] TURING MACHINES AND SPECTRA OF FIRST-ORDER FORMULAS [J].

JONES, ND ;

SELMAN, AL .

JOURNAL OF SYMBOLIC LOGIC, 1974, 39 (01) :139-150

[7]

Ladner R. E., 1975, Theoretical Computer Science, V1, P103, DOI 10.1016/0304-3975(75)90016-X

[8] STRUCTURE OF POLYNOMIAL TIME REDUCIBILITY [J].

LADNER, RE .

JOURNAL OF THE ACM, 1975, 22 (01) :155-171

[9]

Sahni S., 1974, SIAM Journal on Computing, V3, P262, DOI 10.1137/0203021

[10] P-COMPLETE APPROXIMATION PROBLEMS [J].

SAHNI, S ;

GONZALEZ, T .

JOURNAL OF THE ACM, 1976, 23 (03) :555-565

← 1 2 →