CLASSES OF BOUNDED NONDETERMINISM

被引：38

作者：

DIAZ, J

TORAN, J

机构：

[1] Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Barcelona, 08028

来源：

MATHEMATICAL SYSTEMS THEORY | 1990年 / 23卷 / 01期

关键词：

D O I：

10.1007/BF02090764

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study certain language classes located between P and NP that are defined by polynomial-time machines with a bounded amount of nondeterminism. We observe that these classes have complete problems and find a characterization of the classes using robust machines with bounded access to the oracle, obtaining some other results in this direction. We also study questions related to the existence of complete tally sets in these classes and closure of the classes under different types of polynomial-time reducibilities. © 1990 Springer-Verlag New York Inc.

引用

页码：21 / 32

页数：12

共 24 条

[1]

ALDEMAN L, 1979, MITLCSTM131 TECHN RE

[2]

Allender E, 1985, THESIS GEORGIA I TEC

[3]

[Anonymous], 1984, SIAM J COMPUT, V13, P329

[4]

Baker T., 1975, SIAM Journal on Computing, V4, P431, DOI 10.1137/0204037

[5]

BALCAZAR JL, 1984, THESIS FIB

[6]

BALCAZAR JL, 1988, STRUCTURAL COMPLEXIT, V1

[7]

BERMAN P, 1978, 5TH P ICALP, P63

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

BOOK, RV .

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

[9]

BUSS SR, 1987, 19TH P ANN ACM S THE, P123

[10]

CAI JY, 1989, LECT NOTES COMPUT SC, V349, P229

← 1 2 3 →