Bennett, Charles H.; Gill, John Relative to a random oracle A, P(A)non=NP(A)non=co-NP(A) with probability 1. (English) Zbl 0454.68030 SIAM J. Comput. 10, 96-113 (1981). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 13 ReviewsCited in 123 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68Q99 Theory of computing Keywords:relativized computation; probabilistic computation; nondeterministic computation; polynomial immunity; polynomial isomorphism; polynomial reducibility × Cite Format Result Cite Review PDF Full Text: DOI