WITH PROBABILITY ONE, A RANDOM ORACLE SEPARATES PSPACE FROM THE POLYNOMIAL-TIME HIERARCHY

[1] SIGMA-11-FORMULAE ON FINITE STRUCTURES [J]. ANNALS OF PURE AND APPLIED LOGIC, 1983, 24 (01) : 1 - 48

[2] BABAI L, 1986, IN PRESS RANDOM ORAC

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

[4] Baker T. P., 1979, Theoretical Computer Science, V8, P177, DOI 10.1016/0304-3975(79)90043-4

[5] RELATIVE TO A RANDOM ORACLE-A, PA NOT-EQUAL NPA NOT-EQUAL CO-NPA WITH PROBABILITY-1 [J]. SIAM JOURNAL ON COMPUTING, 1981, 10 (01) : 96 - 113

[6] CAI JY, 1986, LECT NOTES COMPUT SC, V223, P105

[7] CHANDRA A, 1981, J ASS COMPUT MACH, V26

[8] PARITY, CIRCUITS, AND THE POLYNOMIAL-TIME HIERARCHY [J]. MATHEMATICAL SYSTEMS THEORY, 1984, 17 (01): : 13 - 27

[9] Hopcroft JE., 2001, INTRO AUTOMATA THEOR, V2nd

[10] SIPSER M, P ACM S THEORY COMPU, P61

[1] SIGMA-11-FORMULAE ON FINITE STRUCTURES [J]. ANNALS OF PURE AND APPLIED LOGIC, 1983, 24 (01) : 1 - 48

[2] BABAI L, 1986, IN PRESS RANDOM ORAC

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

[4] Baker T. P., 1979, Theoretical Computer Science, V8, P177, DOI 10.1016/0304-3975(79)90043-4

[5] RELATIVE TO A RANDOM ORACLE-A, PA NOT-EQUAL NPA NOT-EQUAL CO-NPA WITH PROBABILITY-1 [J]. SIAM JOURNAL ON COMPUTING, 1981, 10 (01) : 96 - 113

[6] CAI JY, 1986, LECT NOTES COMPUT SC, V223, P105

[7] CHANDRA A, 1981, J ASS COMPUT MACH, V26

[8] PARITY, CIRCUITS, AND THE POLYNOMIAL-TIME HIERARCHY [J]. MATHEMATICAL SYSTEMS THEORY, 1984, 17 (01): : 13 - 27

[9] Hopcroft JE., 2001, INTRO AUTOMATA THEOR, V2nd

[10] SIPSER M, P ACM S THEORY COMPU, P61