article Free Access Share on Refining Nondeterminism in Relativizations of Complexity Classes Authors: Xu Mei-rui Harbin University of Science and Technology, Harbin, Heilongjiang, People's Republic of China Harbin University of Science and Technology, Harbin, Heilongjiang, People's Republic of ChinaView Profile , John E. Doner Department of Mathematics, University of California at Santa Barbara, Santa Barbara, CA Department of Mathematics, University of California at Santa Barbara, Santa Barbara, CAView Profile , Ronald V. Book Department of Mathematics, University of California at Santa Barbara, Santa Barbara, CA Department of Mathematics, University of California at Santa Barbara, Santa Barbara, CAView Profile Authors Info & Claims Journal of the ACMVolume 30Issue 3July 1983 pp 677–685https://doi.org/10.1145/2402.322399Published:01 July 1983Publication History 7citation310DownloadsMetricsTotal Citations7Total Downloads310Last 12 Months9Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Due to the work of Baker, Gill and Solovay [SIAM J. Comput., 4 (1975), pp. 431–442] and others, it has become a paradigm that important open questions about complexity classes do not relativize. This paper develops restrictions of the standard oracle machine model for which, in contrast, positive inclusion relationships do relativize. Our results are obtained by uniform simulation techniques. As a consequence, the new oracle machine models exhibit the same computational power as do the corresponding nonrelativized devices.

Consider the classes of formal languages specified by nondeterministic acceptors that operate simultaneously within time bounds from a set $\mathcal{T}$ and space bounds from a set $\mathcal{S}$. How large must the time bounds be in order to obtain all of the languages specified by nondeterministic acceptors that operate within space bounds from $\mathcal{S}$? How large must the space bounds be in order to obtain all of the languages specified by nondeterministic acceptors that operate with time bounds from $\mathcal{T}$? The first question is shown to be equivalent (with appropriate restrictions on $\mathcal{S}$ and $\mathcal{T}$) to the question of whether it matters if the time bounds apply to all of the steps or only to the steps which query the oracle. The second question is shown to be equivalent to the question of whether it matters if the space bounds apply to all of the configurations or only to the configurations in which the oracle is queried. These results generalize a more specific result [6] comparing NP with PSPACE. Also, it is shown that inclusions between the nondeterministic and deterministic time hierarchies fail to translate downwards in some relativized cases.