Deterministic versus nondeterministic time and lower bound problems

被引：3

作者：

Stearns, RE ^{[1
]}

机构：

[1] SUNY Albany, Dept Comp Sci, Albany, NY 12222 USA

来源：

JOURNAL OF THE ACM | 2003年 / 50卷 / 01期

关键词：

theory; algorithms; computational complexity; generic algorithms; generic problems; nondeterminism; NP-completeness; power index; SAT; time complexity;

D O I：

10.1145/602382.602409

中图分类号：

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

学科分类号：

0812 ;

摘要：

引用

页码：91 / 95

页数：5

共 11 条

[1] Semiring-based constraint satisfaction and optimization
Bistarelli, S
Montanari, U
Rossi, F
[J]. JOURNAL OF THE ACM, 1997, 44 (02) : 201 - 236
[2] Cook S.A., 1971, P 3 ANN ACM S THEOR, P151, DOI DOI 10.1145/800157.805047
[3] SHORT PROPOSITIONAL FORMULAS REPRESENT NONDETERMINISTIC COMPUTATIONS
COOK, SA
[J]. INFORMATION PROCESSING LETTERS, 1988, 26 (05) : 269 - 270
[4] ON COMPUTATIONAL COMPLEXITY OF ALGORITHMS
HARTMANIS, J
STEARNS, RE
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 117 (05) : 285 - +
[5] KARP R. M., 1972, COMPLEXITY COMPUTER, P85, DOI DOI 10.1007/978-1-4684-2001-2_9
[6] Robson J. M., 1979, Proceedings of the 2nd Australian Computer Science Conference, P62
[7] KINEMATIC MEASURES FOR SETS OF COLLIDING CONVEX BODIES
SCHNEIDER, R
[J]. MATHEMATIKA, 1978, 25 (49) : 1 - 12
[8] Exploiting structure in quantified formulas
Stearns, RE
Hunt, HB
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 43 (02): : 220 - 263
[9] Turing it's time to award reconsider time lecture
Stearns, Richard Edwin
[J]. Communications of the ACM, 1994, 37 (11) : 95 - 99
[10] POWER INDEXES AND EASIER HARD PROBLEMS
STEARNS, RE
HUNT, HB
[J]. MATHEMATICAL SYSTEMS THEORY, 1990, 23 (04): : 209 - 225

← 1 2 →