The complexity of matrix rank and feasible systems of linear equations

We characterize the complexity of some natural and important problems in linear algebra. In particular, we identify natural complexity classes for which the problems of (a) determining if a system of linear equations is feasible and (b) computing the rank of an integer matrix (as well as other problems) are complete under logspace reductions.?As an important part of presenting this classification, we show that the "exact counting logspace hierarchy" collapses to near the bottom level. We review the definition of this hierarchy below. We further show that this class is closed under NC¹-reducibility, and that it consists of exactly those languages that have logspace uniform span programs (introduced by Karchmer and Wigderson) over the rationals.?In addition, we contrast the complexity of these problems with the complexity of determining if a system of linear equations has an integer solution. Received: June 9, 1997.     

Generalized theorems on relationships among reducibility notions to certain complexity classes

In this paper we give several generalized theorems concerning reducibility notions to certain complexity classes. We study classes that are either (I) closed under NP many-one reductions and polynomial-time conjunctive reductions or (II) closed under coNP many-one reductions and polynomial-time disjunctive reductions. We prove that, for such a classK, (1) reducibility notions of sets toK under polynomial-time constant-round truth-table reducibility, polynomial-time log-Turing reducibility, logspace constant-round truth-table reducibility, logspace log-Turing reducibility, and logspace Turing reducibility are all equivalent and (2) every set that is polynomial-time positive Turing reducible to a set inK is already inK.From these results, we derive some observations on the reducibility notions to C₌P and NP.     

The (Non)Enumerability of the Determinant and the Rank

We investigate the complexity of enumerative approximation of two fundamental problems in linear algebra, computing the rank and the determinant of a matrix. We show that both are as hard to approximate (in the enumerative sense) as to compute exactly. In particular, if there exists an enumerator that, given a matrix over some finite field, outputs a list of constantly many numbers, one of which is guaranteed to be the rank of the matrix, then it can be determined in AC ⁰ (with oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the enumerator is an FL function, then the problem of computing the rank is in FL. For the determinant function we establish the following two results: (1) If the determinant is poly-enumerable in logspace, then it can be computed exactly in FL. (2) For any prime p , if computing the determinant modulo p is (p-1) -enumerable in FL (i.e., if one could eliminate a single possible value for the determinant modulo p ), then the determinant modulo p can be computed in FL. Because there is a close connection between these two functions and logspace counting classes, we hope that our results can give a better understanding of the power of counting in logspace, and the relationships among the complexity classes sandwiched between NL and uniform TC ¹ .     

Multihead Two-Way Probabilistic Finite Automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata. This research was supported by the National Science Foundation under Grant No. CDA 8822724 while the author was at the University of Rochester. An extended abstract of this paper appeared in Proceedings, Second Latin American Symposium, LATIN ’95: Theoretical Informatics, Valparaiso, Chile, April 1995.     

Logspace Optimization Problems and Their Approximability Properties

Logspace optimization problems are the logspace analogues of the well-studied polynomial-time optimization problems. Similarly to them, logspace optimization problems can have vastly different approximation properties even though their underlying decision problems have the same computational complexity. Natural problems - including the shortest path problems for directed graphs, undirected graphs, tournaments, and forests - exhibit such a varying complexity. In order to study the approximability of logspace optimization problems in a systematic way, polynomial-time approximation classes and polynomial-time reductions between optimization problems are transferred to logarithmic space. It is proved that natural problems are complete for different logspace approximation classes. This is used to show that under the assumption L ≠ NL some logspace optimization problems cannot be approximated with a constant ratio; some can be approximated with a constant ratio, but do not permit a logspace approximation scheme; and some have a logspace approximation scheme, but optimal solutions cannot be computed in logarithmic space.     

Multihead two-way probabilistic finite automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata.     

On the Autoreducibility of Functions

This paper studies the notions of self-reducibility and autoreducibility. Our main result regarding length-decreasing self-reducibility is that any complexity class C\mathcal{C} that has a (logspace) complete language and is closed under polynomial-time (logspace) padding has the property that if all C\mathcal{C} -complete languages are length-decreasing (logspace) self-reducible then C í P\mathcal{C}\subseteq \mathrm {P} (C í L\mathcal {C}\subseteq \mathrm {L} ). In particular, this result applies to NL, NP and PSPACE. We also prove an equivalent of this theorem for function classes (for example, for #P). We also show that for several hard function classes, in particular for #P, it is the case that all their complete functions are deterministically autoreducible. In particular, we show the following result. Let f be a #P parsimonious function with two preimages of 0. We show that there are two FP functions h and t such that for all inputs x we have f(x)=t(x)+f(h(x)), h(x)≠x, and t(x)∈{0,1}. Our results regarding single-query autoreducibility of #P functions can be contrasted with random self-reducibility for which it is known that if a #P complete function were random self-reducible with one query then the polynomial hierarchy would collapse.     

Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes

In this paper we classify the complexity of several problems based on Abelian permutation groups and linear congruences using logspace counting classes. The problems we consider were defined by McKenzie & Cook (1987).     

Arithmetic Complexity, Kleene Closure, and Formal Power Series

The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC ¹ and GapL. More precisely, we apply the formal power series operations of inversion and root extraction to these complexity classes. We define a counting version of Kleene closure and show that it is intimately related to inversion and root extraction within GapNC ¹ and GapL. We prove that Kleene closure, inversion, and root extraction are all hard operations in the following sense: there is a language in AC ⁰ for which inversion and root extraction are GapL-complete and Kleene closure is NLOG-complete, and there is a finite set for which inversion and root extraction are GapNC ¹ -complete and Kleene closure is NC ¹ -complete, with respect to appropriate reducibilities. The latter result raises the question of classifying finite languages so that their inverses fall within interesting subclasses of GapNC ¹ , such as GapAC ⁰ . We initiate work in this direction by classifying the complexity of the Kleene closure of finite languages. We formulate the problem in terms of finite monoids and relate its complexity to the internal structure of the monoid. Some results in this paper show properties of complexity classes that are interesting independent of formal power series considerations, including some useful closure properties and complete problems for GapL.     

Semantical Counting Circuits

Abstract. Counting functions can be defined syntactically or semantically depending on whether they count the number of witnesses in a non-deterministic or in a deterministic computation on the input. In the Turing-machine-based model these two ways of defining counting were proven to be equivalent for many important complexity classes. In the circuit-based model it was done for #P, but for low-level complexity classes such as #AC ⁰ and #NC ¹ only the syntactical definitions were considered. We give appropriate semantical definitions for these two classes and prove them to be equivalent to the syntactical ones. We also consider semantically defined probabilistic complexity classes corresponding to AC ⁰ and NC ^{1} and prove that in the case of unbounded error, they are identical to their syntactical counterparts.     

On the Regularity of Petri Net Languages

Petri nets are known to be useful for modeling concurrent systems. Once modeled by a Petri net, the behavior of a concurrent system can be characterized by the set of all executable transition sequences, which in turn can be viewed as a language over an alphabet of symbols corresponding to the transitions of the underlying Petri net. In this paper, we study the language issue of Petri nets from a computational complexity viewpoint. We analyze the complexity of theregularity problem(i.e., the problem of determining whether a given Petri net defines an irregular language or not) for a variety of classes of Petri nets, includingconflict-free,trap-circuit,normal,sinkless,extended trap-circuit,BPP, andgeneralPetri nets. (Extended trap-circuit Petri nets are trap-circuit Petri nets augmented with a specific type ofcircuits.) As it turns out, the complexities for these Petri net classes range from NL (nondeterministic logspace), PTIME (polynomial time), and NP (nondeterministic polynomial time), to EXPSPACE (exponential space). In the process of deriving the complexity results, we develop adecomposition approachwhich, we feel, is interesting in its own right, and might have other applications to the analysis of Petri nets as well. As a by-product, an NP upper bound of the reachability problem for the class of extended trap-circuit Petri nets (which properly contains that of trap-circuit (and hence, conflict-free) and BPP-nets, and is incomparable with that of normal and sinkless Petri nets) is derived.     

On the reducibility of sets inside NP to sets with low information content

This paper studies for various natural problems in NP whether they can be reduced to sets with low information content, such as branches, P-selective sets, and membership comparable sets. The problems that are studied include the satisfiability problem, the graph automorphism problem, the undirected graph accessibility problem, the determinant function, and all logspace self-reducible languages. Some of these are complete for complexity classes within NP, but for others an exact complexity theoretic characterization is not known. Reducibility of these problems is studied in a general framework introduced in this paper: prover-verifier protocols with low-complexity provers. It is shown that all these natural problems indeed have such protocols. This fact is used to show, for certain reduction types, that these problems are not reducible to sets with low information content unless their complexity is much less than what it is currently believed to be. The general framework is also used to obtain a new characterization of the complexity class is the class of all logspace self-reducible sets in L^L-sel.     

Preprocessing of Intractable Problems

Some computationally hard problems, e.g., deduction in logical knowledge bases– are such that part of an instance is known well before the rest of it, and remains the same for several subsequent instances of the problem. In these cases, it is useful to preprocess off-line this known part so as to simplify the remaining on-line problem. In this paper we investigate such a technique in the context of intractable, i.e., NP-hard, problems. Recent results in the literature show that not all NP-hard problems behave in the same way: for some of them preprocessing yields polynomial-time on-line simplified problems (we call them compilable), while for other ones their compilability implies some consequences that are considered unlikely. Our primary goal is to provide a sound methodology that can be used to either prove or disprove that a problem is compilable. To this end, we define new models of computation, complexity classes, and reductions. We find complete problems for such classes, “completeness” meaning they are “the less likely to be compilable.” We also investigate preprocessing that does not yield polynomial-time on-line algorithms, but generically “decreases” complexity. This leads us to define “hierarchies of compilability,” that are the analog of the polynomial hierarchy. A detailed comparison of our framework to the idea of “parameterized tractability” shows the differences between the two approaches.     

On the power of generalized Mod-classes

We investigate the computational power of the new counting class ModP which generalizes the classes Mod _p P,p prime. We show that ModP is polynomialtime truth-table equivalent in power to #P and that ModP is contained in the class AmpMP. As a consequence, the classes PP, ModP, and AmpMP are all Turing equivalent, and thus AmpMP and ModP are not low for MP unless the counting hierarchy collapses to MP. Furthermore, we show that every set in C=P is reducible to some set in ModP via a random many-one reduction that uses only logarithmically many random bits. Hence, ModP and AmpMP are not closed under polynomial-time conjunctive reductions unless the counting hierarchy collapses.     

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.     

The Chain Method to Separate Counting Classes

We introduce a new method to separate counting classes of a special type by oracles. Among the classes, for which this method is applicable, are NP, coNP, US (also called 1-NP), ⊕ P, all other MOD-classes, PP, and C ₌ P, classes of Boolean Hierarchies over the named classes, classes of finite acceptance type, and many more. As an important special case, we completely characterize all relativizable inclusions between classes NP(k) from the Boolean Hierarchy over NP and other classes defined by what we call bounded counting. Received January 1996, and in final form November 1996.     

Expressing uniformity via oracles

We study under what circumstances different uniformity notions for Boolean circuits of logarithmic depth lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access to tally sets that is proved in the present paper:A-uniform circuits of logarithmic depth are of the same computational power asDLOGTIME-uniform circuits of logarithmic depth with oracle access to tally sets inA. This characterization does not only apply to classesA such as logarithmic space or polynomial time, but to all in some sense “well-behaved” classes and especially to all standard complexity classes. We present many applications for this characterization, among them upward separations, depth-uniformity tradeoffs, and inclusion-completeness results for tally languages. The first two authors were partially supported by DFG-La 618/1-1 and the third author was supported by DFG-SFB 0342 “KLARA.”     

Subtractive reductions and complete problems for counting complexity classes

We introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. We show that the main counting complexity classes #P, #NP, as well as all higher counting complexity classes $\#·{\Pi }_k\mathrm{P},k⩾2$, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class #NP (which is the same as the class $\#·\mathrm{coNP}$) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities.     

A study of homogeneity in relational databases

We define four different properties of relational databases which are related tothe notion of homogeneity in classical model theory. The main question for their definition is, for any given database to determine the minimum integer k, such that whenever two k-tuples satisfy the same properties which are expressible in first order logic with up to k variables (FO ^k ), then there is an automorphism which maps each of these k-tuples onto each other. We study these four properties as a means to increase the computational power of subclasses of the reflective relational machines (RRMs) of bounded variable complexity. These were introduced by S. Abiteboul, C. Papadimitriou and V. Vianu and are known to be incomplete. For this sake we first give a semantic characterization of the subclasses of total RRM with variable complexity k (RRM ^k ) for every natural number k. This leads to the definition of classes of queries denoted as Q C Q ^k . We believe these classes to be of interest in their own right. For each k>0, we define the subclass Q C Q ^k as the total queries in the class C Q of computable queries which preserve realization of properties expressible in FO ^k . The nature of these classes is implicit in the work of S. Abiteboul, M. Vardi and V. Vianu. We prove Q C Q ^k =total(RRM ^k ) for every k>0. We also prove that these classes form a strict hierarchy within a strict subclass of total(C Q). This hierarchy is orthogonal to the usual classification of computable queries in time-space-complexity classes. We prove that the computability power of RRM ^k machines is much greater when working with classes of databases which are homogeneous, for three of the properties which we define. As to the fourth one, we prove that the computability power of RRM with sublinear variable complexity also increases when working on databases which satisfy that property. The strongest notion, pairwise k-homogeneity, allows RRM ^k machines to achieve completeness.