NONDETERMINISM WITHIN P

被引：122

作者：

BUSS, JF ^{[1
]}

GOLDSMITH, J ^{[1
]}

机构：

[1] DARTMOUTH COLL, DEPT MATH & COMP SCI, HANOVER, NH 03755 USA

来源：

SIAM JOURNAL ON COMPUTING | 1993年 / 22卷 / 03期

关键词：

NONDETERMINISM; QUASI-LINEAR TIME; COMPUTATIONAL COMPLEXITY;

D O I：

10.1137/0222038

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Classes of machines using very limited amounts of nondeterminism are studied. The P = ? NP question is related to questions about classes lying within P. Complete sets for these classes are given.

引用

页码：560 / 572

页数：13

共 17 条

[1] ON THE COMPLEXITY OF FIXED PARAMETER PROBLEMS [J].

ABRAHAMSON, KR ;

FELLOWS, MR ;

ELLIS, JA ;

MATA, ME .

30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, :210-215

[2]

ABRAHAMSON KR, 1990, DCS141IR U VICT REP

[3] SOME COMBINATORIAL GAME PROBLEMS REQUIRE OMEGA(NK) TIME [J].

ADACHI, A ;

IWATA, S ;

KASAI, T .

JOURNAL OF THE ACM, 1984, 31 (02) :361-376

[4]

ALVAREZ C, 1989, LECT NOTES COMPUT SC, V380, P13

[5] RELATIVIZED ALTERNATION AND SPACE-BOUNDED COMPUTATION [J].

BUSS, JF .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 36 (03) :351-378

[6]

BUSS SR, COMMUNICATION

[7]

COOK SA, 1987, IPL, V26, P269

[8] CLASSES OF BOUNDED NONDETERMINISM [J].

DIAZ, J ;

TORAN, J .

MATHEMATICAL SYSTEMS THEORY, 1990, 23 (01) :21-32

[9]

GESKE JG, 1987, THESIS IOWA STATE U

[10]

GUREVICH Y, 1989, LECT NOTES COMPUT SC, V363, P108

← 1 2 →