IMMUNITY, RELATIVIZATIONS, AND NONDETERMINISM

被引：29

作者：

SCHONING, U ^{[1
]}

BOOK, RV ^{[1
]}

机构：

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

来源：

SIAM JOURNAL ON COMPUTING | 1984年 / 13卷 / 02期

关键词：

D O I：

10.1137/0213023

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：329 / 337

页数：9

共 14 条

[1]

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

[2]

BALCAZAR JL, UNPUB MATH SYSTEMS T

[3]

BALCAZAR JL, UNPUB SIMPLICITY REL

[4] RELATIVE TO A RANDOM ORACLE-A, PA NOT-EQUAL NPA NOT-EQUAL CO-NPA WITH PROBABILITY-1 [J].

BENNETT, CH ;

GILL, J .

SIAM JOURNAL ON COMPUTING, 1981, 10 (01) :96-113

[5] RELATIVIZING TIME, SPACE, AND TIME-SPACE [J].

BOOK, RV ;

WILSON, CB ;

XU, MR .

SIAM JOURNAL ON COMPUTING, 1982, 11 (03) :571-581

[6] BOUNDED QUERY MACHINES - ON NP AND PSPACE [J].

BOOK, RV .

THEORETICAL COMPUTER SCIENCE, 1981, 15 (01) :27-39

[7]

FLAJOLET P, 1974, LECTURE NOTES COMPUT, V14, P446

[8] ORACLE-DEPENDENT PROPERTIES OF THE LATTICE OF NP SETS [J].

HOMER, S ;

MAASS, W .

THEORETICAL COMPUTER SCIENCE, 1983, 24 (03) :279-289

[9]

Hopcroft J.E., 1979, INTRO AUTOMATA THEOR

[10] REFINING NONDETERMINISM IN RELATIVIZED POLYNOMIAL-TIME BOUNDED COMPUTATIONS [J].

KINTALA, CMR ;

FISCHER, PC .

SIAM JOURNAL ON COMPUTING, 1980, 9 (01) :46-53

← 1 2 →