It is shown that, for every k ≥ 0 and every fixed algorithmically random language B, there is a language that is polynomial-time, truth-table reducible in k + 1 queries to B but not truth-table reducible in k queries in any amount of time to any algorithmically random language C. In particular, this yields the separation Pk − tt(RAND) ⫅̸ P(k + 1) − tt(RAND), where RAND is the set of all algorithmically random languages.

In this paper languages “bounded reducible” to algorithmically random languages are studied; these are the languages whose characteristic sequences are algorithmically random (as defined by Martin-Löf [Inform. and Control, 9(), pp. 602–619]); here RAND denotes the class of algorithmically random languages. The reducibilities $ \leqslant ^\mathcal{R} $ are very general but are defined so that if $A \in \mathcal{R}(B)$, then there is a machine M with the properties that $L(M,B) = A$ and every computation of M relative to any oracle halts. Book, Lutz, and Wagner [Math. Systems Theory, 27 (1994), pp. 201–209] studied ALMOST-$\mathcal{R}$, defined to be { $A|$ for almost every B, $A \leqslant _\mathcal{R} B$ }. They showed that ALMOST-$\mathcal{R} = \mathcal{R}({\text{RAND}}) \cap {\text{REC}}$, where ${\text{REC}}$ denotes the class of recursive languages, so that ALMOST-$\mathcal {R}$ is the “recursive part” of $\mathcal{R}({\text{Rand}})$. In this paper this characterization is strengthened by showing that for every$B \in {\text{RAND}}$, ALMOST-$\mathcal{R} = \mathcal{R}({B{RAND}}) \cap {\text{REC}}$. A pair $(A,B)$ of languages is an independent pair of algorithmically random languages if $A \oplus B \in {\text{RAND}}$. In this paper it is shown that for every $\mathcal {R}$ and for every independent pair $(A,B)$, ALMOST-$\mathcal {R} = \mathcal{R}(A) \cap \mathcal{R}(B)$.

It is shown that if a language recognizable in exponential space is bounded truth-table reducible in polynomial time to a language with very high space-bounded Kolmogorov complexity, then it is bounded truth-table reducible in polynomial time to a sparse language. There are a number of corollaries, including the following: (a) no language with very high space-bounded Kolmogorov complexity is $ \leqslant _{btt}^{\text{P}} $-hard for NP, unless ${\text{P}} = {\text{NP}}$; (b) no language with very high space-bounded Kolmogorov complexity is $ \leqslant _{btt}^{\text{P}} $-hard for the class of languages accepted in exponential time.

Cai [J. Comput. System Sci., 38 (1989), pp. 68–85] proved that for almost every set A, ${\operatorname{PH}}(A) \ne {\operatorname{PSPACE}}(A)$. For every set A, there is a restricted relativization of the class ${\operatorname{PSPACE}}(A)$, denoted ${\operatorname{PQH}}(A)$, with the property that ${\operatorname{PQH}}(A)$ lies between ${\operatorname{PH}}(A)$ and ${\operatorname{PSPACE}}(A)$ (as was previously studied in [Theoret. Comput. Sci., 15 (1981), pp. 41–50] and [Theoret. Comput. Sci., 40 (1985), pp. 237–243]). It is shown here that ${\operatorname{PH}} \ne {\operatorname{PSPACE}}$ if and only if, for almost every set A, ${\operatorname{PH}}(A) \ne {\operatorname{PQH}}(A)$. Cai’s proof shows that for almost every set A, ${\operatorname{PQH}}(A) \ne {\operatorname{PSPACE}}(A)$, so that for almost every set A, ${\operatorname{PQH}}(A)$ bounds ${\operatorname{PSPACE}}(A)$ away from ${\operatorname{PH}}(A)$. Bennett and Gill [SIAM J. Comput., 10 (1981), pp.96–113] proved that for almost every set A, ${\operatorname{P}}(A) \ne {\operatorname{NP}}(A)$. For every set A, there is a restricted relativization of the class ${\operatorname{NP}}(A)$ (previously studied in [SIAM J Comput., 13 (1984), pp. 461–487]), denoted ${\operatorname{NP}}_{\text{B}}(A)$, with the property that ${\operatorname{NP}}_{\text{B}}(A)$ lies between ${\operatorname{P}}(A)$ and ${\operatorname{NP}}(A)$. It is known [SIAM J. Comput., 13(1984), pp. 461–487] that ${\operatorname{P}} \ne {\operatorname{NP}}$ if and only if there exists a set A such that ${\operatorname{P}}(A) \ne {\operatorname{NP}}_{\text{B}} (A)$. It is shown here that ${\operatorname{BPP}} \ne {\operatorname{AM}}$ if and only if for almost every set A, ${\operatorname{P}}(A) \ne {\operatorname{NP}}_{\text{B}} (A)$. A result of Kurtz [Inform. and Control, 57 (1983), pp. 40–47] is used to show that for almost every set A, ${\operatorname{NP}}_{\text{B}}(A)$ bounds ${\operatorname{NP}}(A)$ away from ${\operatorname{P}}(A)$. In addition, it is shown that membership in ${\operatorname{PSPACE}}$ can be characterized in terms of the ${\operatorname{PQH}}(\,)$-operator and membership in ${\operatorname{AM}}$ can be characterized in terms of the ${\operatorname{NP}}_{\text{B}} (\, )$-operator. Other results involving quantitative restrictions on access to information from oracles and qualitative restrictions on the use of such information are presented.

We study sets that are truth-table reducible to sparse sets in polynomial time. The principal results are as follows: (1) For every integer $k > 0$, there is a set L and a sparse set S such that $L \leqq _{(k + 1) - tt}^P S$, but there is no sparse set $S'$ such that $L \leqq _{k - tt}^P S'$. (2) There exist a sparse set S and a set L such that $L \leqq _{tt}^P S$ but there is no integer k such that for some sparse $S'$, $L \leqq _{k - tt}^P S'$. (3) The class of sets that are bounded truth-table reducible to tally sets is equal to the class of sets that are many–one reducible to tally sets. (4) The class of sets having polynomial-size circuits is equal to the class of sets that are truth-table reducible to tally sets. Similar results are developed for truth-table reducibilities that are computed nondeterministically in polynomial time or in polynomial space.

The notion of “lowness” was introduced in computational complexity theory by Schöning [J, Comput. Systems Sci., 27 (1983), pp. 14–28] who studied sets in the class NP. This notion may be interpreted as setting an upper bound on the amount of information that can be encoded by a set. Here ideas from previous studies are incorporated in order to capture the notion of a set being exponentially low. The main result asserts the existence of a sparse set E such that ${\operatorname{DEXT}}(E) = {\operatorname{DEXT}}$, i.e., E is “exponentially low,” but E is not in the class P. In contrast, any set with small generalized Kolmogorov complexity that is exponentially low must be in the class P. In addition, we show that for each $k \geqq 2$, any sparse set S that is low with respect to the class $\Sigma _k^E $ of the exponential-time hierarchy (i.e., $\Sigma _k^E {(S) = \Sigma _k^E } $ ) must be in the class $\Sigma _k^P $ of the polynomial-time hierarchy. Similarly, for each $k \geqq 4$, any set with polynomial-size circuits that is low with respect to the class $\Sigma _k^E $ must be in the class $\Sigma _k^P $ .

If C is a class of sets and A is not in C , then an infinite set H is a proper hard core for A with respect to C , if H ⊆ A and for every C ε C such that C ⊆ A , C ⋒ H is finite. It is shown that if C is a countable class of sets of strings that is closed under finite union and finite variation, then every infinite set not in C has a proper hard core with respect to C . In addition, the density of such generalized complexity cores is studied.

Questions about the polynomial-time hierarchy are studied. In particular, the questions, “Does the polynomial-time hierarchy collapse?” and “Is the union of the hierarchy equal to PSPACE?” are considered, along with others comparing the union of the hierarchy with certain probabilistic classes. In each case it is shown that the answer is “yes” if and only if for every sparse set S , the answer is “yes” when the classes are relativized to S if and only if there exists a sparse set S such that the answer is “yes” when the classes are relativized to S . Thus, in each case the question is answered if it is answered for any arbitrary sparse oracle set. Long and Selman first proved that the polynomial-time hierarchy collapses if and only if for every sparse set S , the hierarchy relative to S collapses. This result is re-proved here by a different technique.

We develop the notions of “generalized lowness” for sets in PH (the union of the polynomial-time hierarchy) and of “generalized highness” for arbitrary sets. Also, we develop the notions of “extended lowness” and “extended highness” for arbitrary sets. These notions extend the decomposition of NP into low sets and high sets developed by Schöning [15] and studied by Ko and Schöning [9]. We show that either every sparse set in PH is generalized high or no sparse set in PH is generalized high. Further, either every sparse set is extended high or no sparse set is extended high. In both situations, the former case corresponds to the polynomial-time hierarchy having only finitely many levels while the latter case corresponds to the polynomial-time hierarchy extending infinitely many levels.

We show that several questions about the polynomial-time hierarchy can be answered by answering their counterparts for the polynomial-time hierarchy relativized to an arbitrary sparse oracle set. For each of these questions, the answer will be the same for the hierarchy relativized to S/sub 1/ as it will be for the hierarchy relativized to S/sub 2/ for any choice of S/sub 1/ and S/sub 2/ that are sparse sets, including the choice of S/sub 1/ being empty and S/sub 2/ being nonempty but sparse.

Consider the following open problems: (i) ${\text{P}} = ? {\text{ NP}}$ (ii) ${\text{NP}} = ? {\text{ co-NP}}$; (iii) ${\text{P}} = ? {\text{ PSPACE}}$; (iv) ${\text{NP}} = ? {\text{ PSPACE}}$. In this paper we study these four problems from a particular point of view. To illustrate our approach, consider the first problem. It is known that there exist recursive sets A and B such that ${\text{P}}(A) = {\text{NP}}(A)$ and ${\text{P}}(B) \ne {\text{NP}}(B)$. We study restrictions R on both the deterministic and also the nondeterministic polynomial time-bounded oracle machines such that the following holds: ${\text{P}} = {\text{NP}}$ if and only if for every set A, ${\text{P}}_R (A) = {\text{NP}}_R (A)$. The restrictions are “quantitative” in the sense that the size of the set of strings queried by the oracle in computations of a machine on an input is bounded by a polynomial in the length of the input. We study several different ways of specifying such quantitative restrictions, each of which has the desired property.

It is known [8], [13] that there is a recursive set A such that ${\text{NP }}(A)$ contains a set that is ${\text{P }}(A)$ -immune; that is, there is an infinite set $L \in {\text{NP}}(A)$ such that no infinite subset of L is in ${\text{P}}(A)$. The first result generalizes this fact to situations where the running times of the machines specifying the “larger” class bound the size of the sets of strings queried in the computation trees of the machines specifying the “smaller” class. The second result is of a different type. For relativized complexity classes specified by bounds on the number of oracle queries and the number of nondeterministic steps allowed in computations, it is known [14] that one can describe a set A such that there is an infinite hierarchy of classes relative to A where each new class in the hierarchy is obtained by increasing the amount of nondeterminism. Here it is shown that the conditions allowing infinite hierarchies to exist also allow for each $i \geqq 0$, the existence of a set in the $(i + 1)$st class which has no infinite subset in the ith class.

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.

Confluent and other types of finite Thue systems are studied.Sufficlem condmons are developed for every congruence class and every fimte union of congruence classes defined by such a system to be a determtmsttc context-free language.It is shown that the word problem for Church-Rosser systems is decidable m hnear t~me Categories and Subject Descriptors F 4 2 [Mathematical Logic and Formal Languages] Grammars and Other Rewriting Systems--Thue systems, F 4 3 [Mathematical Logic and Formal Languages]: Formal Languages--deczswn problems

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.

If $h_1 $, $h_2 $ are two homomorphisms, then the equality set$\operatorname{Eq}(h_1 ,h_2 )$ of $h_1 $, $h_2 $ is $\operatorname{Eq} (h_1 ,h_2 ) = \{ w | h_1 (w) = h_2 (w)\} $. In this paper it is shown how to characterize complexity classes of formal languages in terms of equality sets of pairs of homomorphisms with bounded balance. In addition the complete twin shuffle language is investigated, and it is shown that for alphabets with at least two letters, this language cannot be represented as the equality set of a pair of homomorphisms unless both homomorphisms are erasing and have linear bounded balance.

It is shown that every uniquely decipherable code with just two codewords has finite delay. In addition, if a uniquely decipherable code with just two codewords is full, then it is trivial.

A characterization of PSPACE in terms of the regular sets and certain algebraic closure operations is developed. It is shown that NP = PSPACE if and only if NP is closed under a form of the transitive closure operation.

^RSTRACr Using the operation of homomorphlc replication, some restrictions of that operation, and the Boolean operations, simple and uniform characterizations of the following classes of languages are developed.the recurslvely enumerable sets, the arithmetical sets, the languages accepted m real time by nondetermlmstlc reversal-bounded mult~tape Turlng machines, the rudimentary languages, NP, and the extended rudimentary languages

The intersection closure and the closure under homomorphic replication and intersection of certain classes of languages are studied and related to a specific class $\mathcal{L}_{{\text{BNP}}} $ of languages defined in [5]. The proof techniques rely on the “set-theoretic algebra” of language theory instead of arguments involving abstract families of acceptors.

The purpose of this paper is to establish the following result.

A Turing machine whose behavior is restricted so that each read-write head can change its direction only a bounded number of times is reversal-bounded. Here we consider nondeterministic multitape acceptors which are both reversal-bounded and also operate in linear time. Our main result shows that such an acceptor need have only three pushdown stores as auxiliary storage, each pushdown store need make only one reversal, and the acceptor can operate in real time.

If every non-context-free rewriting rule of a context-sensitive (with erasing) grammar has as left context a string of terminal symbols and the left context is at least as long as the right context, then the language generated is context-free. If every non-context-free rewriting rule of a context-sensitive (with erasing) grammar has as left and right context strings of terminal symbols, then the language generated is context-free.

The family NP (P) of languages accepted by nondeterministic (deterministic) Turing machines operating in polynomial time is distinct from many well-known families of languages defined by tape-bounded or time-bounded Turing machines. In particular, it is shown that NP (P) is not equal to the family of context-sensitive languages, the family of languages accepted by deterministic linear bounded automata, or the family of languages accepted by deterministic Turing machines operating within exponential time.

A regular expression is called unambiguous if every tape in the event can be generated from the expression in one way only. The flow-graph technique for constructing an expression is shown to preserve ambiguities of the graph, and thus, if the graph is that of a deterministic automaton, the expression is unambiguous. A procedure for generating a nondeterministic automaton which preserves the ambiguities of the given regular expression is described. Finally, a procedure for testing whether a given expression is ambiguous is given.

Complexity classes of formal languages defined by time- and tape-bounded Turing acceptors are studied with the aim of showing sufficient conditions for these classes to be AFLs and to be principal AFLs.

Quasi-realtime languages are the languages accepted by nondeterministic multitape Turing machines in real time. The family of quasi-realtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. It is identical with the family of languages accepted by nondeterministic multitape Turing machines in linear time. Every quasi-realtime language can be accepted in real time by a non-deterministic one stack, one pushdown store machine, and can be expressed as the length-preserving homomorphic image of the intersection of three context-free languages.