The complexity of ranking simple languages

Ranking is the problem of computing for an input string its lexicographic index in a given (fixed) language. This paper concerns the complexity of ranking. We show that ranking languages accepted by 1-way unambiguous auxiliary pushdown automata operating in polynomial time is inNC ⁽²⁾. We also prove negative results about ranking for several classes of simple languages.C is rankable in deterministic polynomial time iffP=P ^#P , whereC is any of the following six classes of languages: (1) languages accepted by logtime-bounded nondeterministic Turing machines, (2) languages accepted by (uniform) families of unbounded fan-in circuits of constant depth and polynomial size, (3) languages accepted by 2-way deterministic pushdown automata, (4) languages accepted by multihead deterministic finite automata, (5) languages accepted by 1-way nondeterministic logspace-bounded Turing machines, and (6) finitely ambiguous linear context-free languages.This research was partially supported by the National Science Foundation under Grant DCR-8696097. A preliminary version of this paper was presented at the 3rd Annual Structure in Complexity Theory Conference, Washington, DC, June 1988.     

Qualitative relativizations of complexity classes

The principal result of this paper is a “positive relativization” of the open question “P = ?$\text{NP ? co-NP}$.” That is, the nondeterministic polynomial time-bounded oracle Turing machine endowed with designated accepting states and with designated rejecting states is considered, and suitable restrictions R of this device are developed such that $\text{P = NP ? co-NP}$ if and only if for every oracle D, P(D) = NP_R(D), where NP_R(D) is the class of languages L?NP(D) that are accepted by oracle machines operating with restrictions R. Positive relativizations are obtained for the P = ? $\text{U}$ ? co - $\text{U}$ and $\text{U}$ = ? NP questions also, where $\text{U}$ is the class of languages L in NP accepted by nondeterministic machines that operate in polynomial time and that have for each input at most one accepting computation. The restrictions developed here are “qualitative” in the sense that they restrict the form and pattern of access to the oracle. In contrast, a previous paper [3] developed quantitative relativizations-the number of distinct queries to the oracle is restricted-but no quantitative positive relativization of $\text{P = ? NP ? co-NP}$ is known.     

Completeness for nondeterministic complexity classes

We demonstrate differences between reducibilities and corresponding completeness notions for nondeterministic time and space classes. For time classes the studied completeness notions under polynomial-time bounded (even logarithmic-space bounded) reducibilities turn out to be different for any class containingNE. For space classes the completeness notions under logspace reducibilities can be separated for any class properly containingLOGSPACE. Key observation in obtaining the separations is the honesty property of reductions, which was recently observed to hold for the time classes and can be shown to hold for space classes.The work of S. Homer was supported in part by National Science Foundation Grants MIP-8608137 and CCR-8814339 and a Fulbright-Hays Research Fellowship. Some of this research was done while he was a Guest Professor at the Mathematics Institute of Heidelberg University.     

Bi-immune sets for complexity classes

An infinite and co-infinite setA is bi-immune for a complexity classC if neitherA nor its complement has an infinite subset inC. We prove various equivalent characterizations of this notion. Also, we introduce a stronger version of bi-immunity and show how both notions relate to density and other properties of sets in EXPTIME.This research was performed while the authors were visiting the Department of Mathematics, University of California, Santa Barbara, Ca. 93106, U.S.A., and was supported in part by the U.S.A.-Spanish Joint Committee for Educational and Cultural Affairs, by the Deutsche Forschungsgemeinschaft, and by the National Science Foundation under Grants MCS80-11979 and MCS83-12472.     

The query complexity of learning DFA

It is known that the class of deterministic finite automata is polynomial time learnable by using membership and equivalence queries. We investigate the query complexity of learning deterministic finite automata, i.e., the number of membership and equivalence queries made during the process of learning. We extend a known lower bound on membership queries to the case of randomized learning algorithms, and prove lower bounds on the number of alternations between membership and equivalence queries. We also show that a trade-off exists, allowing us to reduce the number of equivalence queries at the price of increasing the number of membership queries.     

The complexity of model classes, and smoothing noisy data

We consider the problem of smoothing a sequence of noisy observations using a fixed class of models. Via a deterministic analysis, we obtain necessary and sufficient conditions on the noise sequence and model class that ensure that a class of natural estimators gives near-optimal smoothing. In the case of i.i.d. random noise, we show that the accuracy of these estimators depends on a measure of complexity of the model class involving covering numbers. Our formulation and results are quite general and are related to a number of problems in learning, prediction, and estimation. As a special case, we consider an application to output smoothing for certain classes of linear and nonlinear systems. The performance of output smoothing is given in terms of natural complexity parameters of the model class, such as bounds on the order of linear systems, the -norm of the impulse response of stable linear systems, or the memory of a Lipschitz nonlinear system satisfying a fading memory condition.     

Characterizing polynomial complexity classes by reducibilities

A series of recent results has characterized membership in certain complexity classes in terms of specific types of reductions: a set is in the class if and only if it is reducible to almost every set. We define a new notion of reducibility which characterizes the classes _k ^p ,k>0, of the polynomial-time hierarchy in this way. As an application, we show that the levels of the polynomial-time hierarchy are distinct if and only if uniform witnesses to this separation exist.This research was supported in part by the National Science Foundation under Grant CCR86-11980.     

The true sample complexity of active learning

We describe and explore a new perspective on the sample complexity of active learning. In many situations where it was generally believed that active learning does not help, we show that active learning does help in the limit, often with exponential improvements in sample complexity. This contrasts with the traditional analysis of active learning problems such as non-homogeneous linear separators or depth-limited decision trees, in which Ω(1/ε) lower bounds are common. Such lower bounds should be interpreted carefully; indeed, we prove that it is always possible to learn an ε-good classifier with a number of samples asymptotically smaller than this. These new insights arise from a subtle variation on the traditional definition of sample complexity, not previously recognized in the active learning literature.     

Logical and schematic characterization of complexity classes

We consider classes of well-known program schemes from a complexity theoretic viewpoint. We define logics which express all those problems solvable using our program schemes and show that the class of problems so solved or expressed coincides exactly with the complexity classPSPACE (our problems are viewed as sets of finite structures over some vocabulary). We derive normal form theorems for our logics and use these normal form theorems to show that certain problems concerning acceptance and termination of our program schemes and satisfiability of our logical formulae arePSPACE-complete. Moreover, we show that a game problem, seemingly disjoint from logic and program schemes, isPSPACE-complete using the results described above. We also highlight similarities between the results of this paper and the literature, so providing the reader with an introduction to this area of research.     

The unfalsified control concept and learning

Without a plant model or other prejudicial assumptions, a theory is developed for identifying control laws which are consistent with performance objectives and past experimental data-possibly before the control laws are ever inserted in the feedback loop. The theory complements model-based methods such as H^∞-robust control theory by providing a precise characterization of how the set of suitable controllers shrinks when new experimental data is found to be inconsistent with prior assumptions or earlier data. When implemented in real time, the result is an adaptive switching controller. An example is included     

Complete sets and closeness to complexity classes

We consider two setsA andB to be close to each other if the census of their symmetric difference,A B, is a slowly increasing function (e.g. a polynomial.) The classes of sets which are polynomially close to some set in a complexity classC (likeP) are studied and characterized. We investigate the question whether complete sets forNP or EXPTIME can be polynomially close to a set inP. Some of the obtained results strengthen or generalize results by Yesha [24], e.g. it is shown that no EXPTIME-hard set can be polynomially close to any set inP.     

Relativizing small complexity classes and their theories

Existing definitions of the relativizations of NC ¹, L and NL do not preserve the inclusions \({{\bf NC}^1 \subseteq {\bf L}, {\bf NL}\subseteq {\bf AC}^1}\). We start by giving the first definitions that preserve them. Here for L and NL we define their relativizations using Wilson’s stack oracle model, but limit the height of the stack to a constant (instead of log(n)). We show that the collapse of any two classes in \({\{{\bf AC}^0 (m), {\bf TC}^0, {\bf NC}^1, {\bf L}, {\bf NL}\}}\) implies the collapse of their relativizations. Next we exhibit an oracle α that makes AC ^k (α) a proper hierarchy. This strengthens and clarifies the separations of the relativized theories in Takeuti (1995). The idea is that a circuit whose nested depth of oracle gates is bounded by k cannot compute correctly the (k + 1) compositions of every oracle function. Finally, we develop theories that characterize the relativizations of subclasses of P by modifying theories previously defined by the second two authors. A function is provably total in a theory iff it is in the corresponding relativized class, and hence, the oracle separations imply separations for the relativized theories.     

The complexity of transformation of normal forms for characteristic functions of classes

We establish new results on the computational complexity of recognition procedures based on constructing normal forms of characteristic functions of classes.     

Strong separation of learning classes

Abstract

Suppose LC ₁ and LC ₂ are two machine learning classes each based on a criterion of success. Suppose, for every machine which learns a class of functions according to the LC ₂ criterion of success, there is a machine which learns this class according to the LC ₂ criterion. In the case where the converse does not hold LC, is said to be separated from LC ₂. It is shown that for many such separated learning classes from the literature a much stronger separation holds: (?𝒞∈LC ₁) (?𝒞' ∈LC ₂ - LC ₁(( [' ?𝒞] It is also shown that there is a pair of separated learning classes from the literature for which the stronger separation above does not hold. A philosophical heuristic toward the design of artificially intelligent learning programs is presented with each strong separation result.     

Generalized lowness and highness and probabilistic complexity classes

We introduce generalized notions of low and high complexity classes and study their relation to structural questions concerning bounded probabilistic polynomial-time complexity classes. We show, for example, that for a bounded probabilistic polynomial-time complexity class =BP _k ^P ,L =H implies that the polynomial hierarchy collapses to . This extends Schöning's result for = _k ^P (L andH are the low and high sets defined by ). We also show, with one exception, that containment relations between the bounded probabilistic classes and the polynomial hierarchy are preserved by their low and high counterparts.LBPP andLBPNP are characterized asNP BPP andNP co-BPNP, respectively. These characterizations are then used to recover Boppana, Hastad, and Zachos's result that if co-NP BPNP, then the polynomial hierarchy collapses toBPNP, and Ko's result that ifNP BPP, then the polynomial hierarchy collapses toBPP.     

Equilibria,fixed points,and complexity classes

Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are, respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in two-player normal form games, and (mixed) Nash equilibria in normal form games with three (or more) players. This paper reviews the underlying computational principles and the corresponding classes.