One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some natural NP-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows. 1. First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs. 2. Then, we observe that McKTP is NP-complete under polynomial-time randomized reductions. 3. Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP. Thus the existence of OWFs is inextricably linked to the average-case hardness of this NP-complete problem. In fact, building on recent results of Ren and Santhanam (CCC 2021), we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs.

A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT complexity of a string). Both MKTP and MCSP are hard for SZK (Statistical Zero Knowledge) under BPP-Turing reductions; neither is known to be NP-complete. Recently, some hardness results for MKTP were proved that are not (yet) known to hold for MCSP. In particular, MKTP is hard for DET (a subclass of P) under nonuniform ≤^{NC^0}_m reductions. In this paper, we improve this, to show that the complement of MKTP is hard for the (apparently larger) class NISZK_L under not only ≤^{NC^0}_m reductions but even under projections. Also, the complement of MKTP is hard for NISZK under ≤^{P/poly}_m reductions. Here, NISZK is the class of problems with non-interactive zero-knowledge proofs, and NISZK_L is the non-interactive version of the class SZK_L that was studied by Dvir et al. As an application, we provide several improved worst-case to average-case reductions to problems in NP, and we obtain a new lower bound on MKTP (which is currently not known to hold for MCSP).

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL∩co-UL), which is contained in AC². Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^{10}n) (corresponding to the complexity class AC^{10} ⊆ NC^{11}). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.

Variants of the Exponential Time Hypothesis (ETH) have been used to derive lower bounds on the time complexity for certain problems, so that the hardness results match long-standing algorithmic results. In this paper, we consider a syntactically defined class of problems, and give conditions for when problems in this class require strongly exponential time to approximate to within a factor of (1-epsilon) for some constant epsilon > 0, assuming the Gap Exponential Time Hypothesis (Gap-ETH), versus when they admit a PTAS. Our class includes a rich set of problems from additive combinatorics, computational geometry, and graph theory. Our hardness results also match the best known algorithmic results for these problems.

We study the computational power of deciding whether a given truth table can be described by a circuit of a given size (the minimum circuit size problem, or MCSP for short) and of the variant denoted as MKTP, where circuit size is replaced by a polynomially related Kolmogorov measure. Prior to our work, all reductions from supposedly intractable problems to MCSP/MKTP hinged on the power of MCSP/MKTP to distinguish random distributions from distributions produced by hardness-based pseudorandom generator constructions. We develop a fundamentally different approach inspired by the well-known interactive proof system for the complement of graph isomorphism (GI). It yields a randomized reduction with zero-sided error from GI to MKTP. We generalize the result and show that GI can be replaced by any isomorphism problem for which the underlying group satisfies some elementary properties. Instantiations include linear code equivalence, permutation group conjugacy, and matrix subspace conjugacy. Along the way we develop encodings of isomorphism classes that are efficiently decodable and achieve compression that is at or near the information-theoretic optimum; those encodings may be of independent interest.

Cost register automata (CRAs) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the tropical semiring (N U {infinity},\min,+) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC^1 when the semiring is (Z,+,x) or (Gamma^*,max,concat). This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC^1 versus GapNC^1.

We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP^QBF is known to be complete for PSPACE under ZPP reductions. We show that it is not complete under logspace reductions, and indeed it is not even hard for TC under uniform AC^0 reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures.

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC1= Log(CFL)) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

We observe that many important computational problems in NC 1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial-size TC 0 circuits if and only if it has TC 0 circuits of size n 1+ϵ for every ϵ> 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC 1 and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC 0 circuits of size n 1+ϵ d . If one were able to improve this lower bound to show that there is some constant ϵ> 0 (independent of the depth d ) such that every TC 0 circuit family recognizing BFE has size at least n 1+ϵ , then it would follow that TC 0 ≠ NC 1 . We show that proving lower bounds of the form n 1+ϵ is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as ACC 0 , TC 0 and NC 1 via existing “natural” approaches to proving circuit lower bounds. We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC 0 and AC 0 [6] circuits of size n 1+ c for some constant c depending on d .

We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: (a) the Blum–Shub–Smale model of computation over the reals; and (b) a problem we call the “generic task of numerical computation,” which captures an aspect of doing numerical computation in floating point, similar to the “long exponent model” that has been studied in the numerical computing community. We show that both of these approaches hinge on the question of understanding the complexity of the following problem, which we call PosSLP: Given a division-free straight-line program producing an integer N, decide whether $N>0$. In the Blum–Shub–Smale model, polynomial-time computation over the reals (on discrete inputs) is polynomial-time equivalent to PosSLP when there are only algebraic constants. We conjecture that using transcendental constants provides no additional power, beyond nonuniform reductions to PosSLP, and we present some preliminary results supporting this conjecture. The generic task of numerical computation is also polynomial-time equivalent to PosSLP. We prove that PosSLP lies in the counting hierarchy. Combining this with work of Tiwari, we obtain that the Euclidean traveling salesman problem lies in the counting hierarchy—the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE. In the course of developing the context for our results on arithmetic circuits, we present some new observations on the complexity of the arithmetic circuit identity testing (ACIT) problem. In particular, we show that if $n!$ is not ultimately easy, then ACIT has subexponential complexity.

This issue contains the polished, extended, and fully refereed versions of a selection of papers that were presented at the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007), which was held June 11–13, 2007, in San Diego, California, in conjunction with the Federated Computing Research Conference (FCRC 2007). Unrefereed preliminary versions of these papers were published by ACM in the proceedings of the meeting, along with the other papers presented at the symposium. The conference program included 77 papers, selected from among a record 312 submissions by a program committee chaired by Uriel Feige and consisting of Eric Allender, Andris Ambainis, Chandra Chekuri, Artur Czumaj, Yevgeniy Dodis, Michel Goemans, Martin Grohe, Russell Impagliazzo, Valerie King, Robert Kleinberg, Vladlen Koltun, Robi Krauthgamer, Jiří Matoušek, Milena Mihail, Ryan O'Donnell, Vijaya Ramachandran, Leonard Schulman, Maxim Sviridenko, Mikkel Thorup, Salil Vadhan, and Santosh Vempala. The authors of 14 of these 77 papers were invited to submit revised versions for this special section; nine accepted the invitation, although one paper was not completed in time to appear in this volume. One paper that appears in this special issue (by Haitner et al.) is the result of merging a STOC 2007 paper with a FOCS 2006 paper that had been invited for the special issue of SIAM Journal on Computing devoted to FOCS 2006; the authors felt that a single, streamlined paper would be more beneficial to the community, and the editors concurred. The paper by Martin Fürer appearing in this issue is one of two papers that shared the award for best paper in STOC 2007. All of these papers were refereed in accordance with the stringent standards of SIAM Journal on Computing. We thank the anonymous referees and the authors for their efforts, resulting in substantial improvements in the end product. We also thank the rest of the program committee members for their help in the selection process. The three of us listed below are honored to have had the opportunity to serve as guest editors in preparing this special issue.

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon ≫ 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC^1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC^0 circuits of size n^{1+\epsilon_d}. If one were able to improve this lower bound to show that there is some constant \epsilon≫0 such that every TC^0 circuit family recognizing BFE has size n^{1+\epsilon}, then it would follow that TC^0 \not= \NC^1. We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC^0 and AC^0[6] circuits of size n^{1+c} for some constant c depending on d.

For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a k-term disjunctive normal form (DNF), and Min-Circuit (also called the minimum circuit size problem (MCSP)), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [Some NP-Complete Set Covering Problems, manuscript, 1979], which is from Circuit-SAT. We then give a more complex reduction, yielding the result that Min-DNF cannot be approximated to within a factor smaller than $(\log N)^{\gamma}$, for some constant $\gamma>0$, assuming that NP is not contained in quasi-polynomial time. The standard greedy algorithm for Set Cover is often used in practice to approximate Min-DNF. The question of whether Min-DNF can be approximated to within a factor of $o(\log N)$ remains open, but we construct an instance of Min-DNF on which the solution produced by the greedy algorithm is $\Omega(\log N)$ larger than optimal. Finally, we turn to the question of approximating circuit size for slightly more general classes of circuits. DNF formulas are depth-two circuits of AND and OR gates. Depth-d circuits are denoted by $AC^0_d$. We show that it is hard to approximate the size of $AC^0_d$ circuits (for large enough d) under cryptographic assumptions.

We study the complexity of reachability problems on various classes of grid graphs. Reachability on certain classes of grid graphs gives natural examples of problems that are hard for NC1under AC0reductions but are not known to be hard far L; they thus give insight into the structure of L. In addition to explicating the structure of L, another of our goals is to expand the class of digraphs for which connectivity can be solved in logspace, by building on the work of Jakoby et al. (2001), who showed that reachability in series-parallel digraphs is solvable in L. We show that reachability for single-source multiple sink planar dags is solvable in L

We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the following problem, which we call PosSLP; given a division-free straight-line program producing an integer N, decide whether N > 0. We show that PosSLP lies in the counting hierarchy, and combining our results with work of Tiwari, we show that the Euclidean traveling salesman problem lies in the counting hierarchy - the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE.

For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a k-term DNF, and Min-Circuit (also called MCSP), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek (1979), which is from Circuit-SAT. We then give a more complex reduction, yielding the result that Min-DNF cannot be approximated to within a factor smaller than (log N)/sup /spl Upsi//, for some constant /spl Upsi/ > 0, assuming that NP is not contained in quasipolynomial time. The standard greedy algorithm for set cover is often used in practice to approximate Min-DNF. The question of whether Min-DNF can be approximated to within a factor of o(log N) remains open, but we construct an instance of Min-DNF on which the solution produced by the greedy algorithm is /spl Omega/(log N) larger than optimal. Finally, we extend known hardness results for Min-TC/sup 0//sub d/ to obtain new hardness results for Min-AC/sup 0//sub d/, under cryptographic assumptions.

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let ${{R_{\rm C}}}, {{R_{\rm Kt}}}, {{R_{\rm KS}}}, {{R_{\rm KT}}}$ be the sets of strings x having complexity at least $|x|/2$, according to the usual Kolmogorov complexity measure ${\mbox{\rm C}}$, Levin's time-bounded Kolmogorov complexity ${\mbox{\rm Kt}}$ [L. Levin, Inform. and Control, 61 (1984), pp. 15-37], a space-bounded Kolmogorov measure ${\mbox{\rm KS}}$, and a new time-bounded Kolmogorov complexity measure ${\mbox{\rm KT}}$, respectively. Our main results are as follows: \begin{remunerate} \item ${{R_{\rm KS}}}$ and ${{R_{\rm Kt}}}$ are complete for ${{\rm{PSPACE}}}$ and {\mbox{\rm EXP}}, respectively, under ${\mbox{\rm P/poly}}$-truth-table reductions. Similar results hold for other classes with ${{\rm{PSPACE}}}$-robust Turing complete sets. \item ${\mbox{\rm EXP}} = {\mbox{\rm NP}}^{{{R_{\rm Kt}}}}.$ \item ${{\rm{PSPACE}}} = {\mbox{\rm ZPP}}^{{{R_{\rm KS}}}} \subseteq {\mbox{\rm P}}^{{{R_{\rm C}}}}$. \item The Discrete Log, Factoring, and several lattice problems are solvable in ${\mbox{\rm BPP}}^{{{R_{\rm KT}}}}$. \end{remunerate} Our hardness result for ${{\rm{PSPACE}}}$ gives rise to fairly natural problems that are complete for ${{\rm{PSPACE}}}$ under ${\mbox{$\leq^{\rm p}_{\rm T}$}}$ reductions, but not under ${\mbox{$\leq^{\rm log}_{\rm m}$}}$ reductions. Our techniques also allow us to show that all computably enumerable sets are reducible to ${{R_{\rm C}}}$ via ${\mbox{\rm P/poly}}$-truth-table reductions. This provides the first "efficient" reduction of the halting problem to ${{R_{\rm C}}}$.

We show that ACC/sup 0/ is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC/sup 0/. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of planarity, including crossing number and thickness. We show that thickness two already suffices to capture all of NC/sup 1/.

.

.

We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [E. Allender (2001), E. Allender et al., (2002)]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt and KNT) and examine the properties of these measures using constructions of hitting set generators for nondeterministic circuits [P. B. Miltersen et al., (1999), R. Shaltiel et al., (2001)]. We observe that KNt bears many similarities to the nondeterministic distinguishing complexity CND of [H. Buhrman et al., (2002)]. This motivates the definition of a new notion of time-bounded distinguishing complexity KDt, as an intermediate notion with connections to the class FewEXP. The set of KDt-random strings is complete for EXP under P/poly reductions. Most of the notions of resource-bounded Kolmogorov complexity discussed here and in [E. Allender (2001), E. Allender et al., (2002)] have close connections to circuit size (on different types of circuits). We extend this framework to define notions of Kolmogorov complexity KB and KF that are related to branching program size and formula size, respectively. The sets of KB- and KF-random strings lie in coNP; we show that oracle access to these sets enables one to factor Blum integers. We obtain related intractability results for approximating minimum formula size, branching program size, and circuit size. The NEXP/spl sube/NC and NEXP/spl sube/L/poly questions are shown to be equivalent to conditions about the KF and KB complexity of sets in P.

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.

We establish a new hardness result that shows that the difficulty of plan- ning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed family of fac- tored MDPs with linear rewards whose optimal policies and value func- tions simply cannot be represented succinctly in any standard parametric form. Previous hardness results indicated that computing good policies from the MDP parameters was difficult, but left open the possibility of succinct function approximation for any fixed factored MDP. Our result applies even to policies which yield a polynomially poor approximation to the optimal value, and highlights interesting connectionswith the com- plexity class of Arthur-Merlin games.

Integer division has been known to lie in P-uniform TC/sup 0/ since the mid-1980s, and recently this was improved to L-uniform TC/sup 0/. At the time that the results in this paper were proved and submitted for conference presentation, it was unknown whether division lay in DLOGTIME-uniform TC/sup 0/ (also known as FOM). We obtain tight bounds on the uniformity required for division, by showing that division is complete for the complexity class FOM+POW obtained by augmenting FOM with a predicate for powering modulo small primes. We also show that, under a well-known number-theoretic conjecture (that there are many "smooth" primes), POW (and hence division) lies in FOM. Building on this work, Hesse has shown recently that division is in FOM [17]. The essential idea in the fast parallel computation of division and related problems is that of Chinese remainder representation (CRR)-storing a number in the form of its residues modulo many small primes. The fact that CRR operations can be carried out in log space has interesting implications for small space classes. We define two versions of s(n) space for s(n)=o(log n): dspace(s(n)) as the traditional version where the worktape begins blank, and DSPACE(s(n)) where the space bound is established by endmarkers before the computation starts. We present a new translational lemma, and derive as a consequence that (for example), if one can improve the result of Hartmanis and Berman (1976) that {0/sup n/: n is prime} /spl notin/ dspace (log log n) to show that {0/sup n/: n is prime} /spl notin/ DSPACE (log log n), it would follow that L/spl ne/NP.

Extends the lower-bound techniques of L. Fortnow (2000) to the unbounded-error probabilistic model. A key step in the argument is a generalization of V.A. Nepomnjas/spl caron/c/spl caron/ii/spl breve/'s (1970) theorem from the Boolean setting to the arithmetic setting. This generalization is made possible due to the recent discovery of logspace-uniform TC/sup 0/ circuits for iterated multiplication (A. Chiu et al., 2000). As an example of the sort of lower bounds that we obtain, we show that MAJ-MAJSAT is not contained in PrTiSp(n/sup 1+o(1)/, n/sup /spl epsiv//) for any /spl epsiv/<1. We also extend one of Fortnow's lower bounds, from showing that S~A~T~ does not have uniform NC/sup 1/ circuits of size n/sup 1+o(1)/, to a similar result for SAC/sup 1/ circuits.

Controlled stochastic systems occur in science engineering, manufacturing, social sciences, and many other cntexts. If the systems is modeled as a Markov decision process (MDP) and will run ad infinitum , the optimal control policy can be computed in polynomial time using linear programming. The problems considered here assume that the time that the process will run is finite, and based on the size of the input. There are mny factors that compound the complexity of computing the optimal policy. For instance, there are many factors that compound the complexity of this computation. For instance, if the controller does not have complete information about the state of the system, or if the system is represented in some very succint manner, the optimal policy is provably not computable in time polynomial in the size of the input. We analyze the computational complexity of evaluating policies and of determining whether a sufficiently good policy exists for a MDP, based on a number of confounding factors, including the observability of the system state; the succinctness of the representation; the type of policy; even the number of actions relative to the number of states. In almost every case, we show that the decision problem is complete for some known complexity class. Some of these results are familiar from work by Papadimitriou and Tsitsiklis and others, but some, such as our PL-completeness proofs, are surprising. We include proofs of completeness for natural problems in the as yet little-studied classes NP PP .

We show that in the context of nonuniform complexity, nondeterministic logarithmic space bounded computation can be made unambiguous. An analogous result holds for the class of problems reducible to context-free languages. In terms of complexity classes, this can be stated as NL/poly = UL/poly,\\ LogCFL/poly = UAuxPDA($\log n, n^{O(1)}$)/poly.

Recent work by Bernasconi, Damm and Shparlinski proved lower bounds on the circuit complexity of the square-free numbers, and raised as an open question if similar (or stronger) lower bounds could be proved for the set of prime numbers. In this short note, we answer this question affirmatively, by showing that the set of prime numbers (represented in the usual binary notation) is not contained in AC/sup 0/ [p] for any prime p. Similar lower bounds are presented for the set of square-free numbers, and for the problem of computing the greatest common divisor of two numbers.

We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that the complexity class LogFew coincides with NL in the nonuniform setting. Finally, we provide evidence that our results also hold in the uniform setting.

Continuing a line of investigation that has studied the function classes P, we study the class of functions AC/sup 0/. One way to define AC/sup 0/ is as the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fanin addition and multiplication gates. In contrast to the preceding function classes, for which we know no nontrivial lower bounds, lower bounds for AC/sup 0/ follow easily from established circuit lower bounds. One of our main results is a characterization of TC/sup 0/ in terms of AC/sup 0/: A language A is in TC/sup 0/ if and only if there is a AC/sup 0/ function f and a number k such that x/spl isin/A/spl hArr/f(x)=2/sup |x|k/. Using the naming conventions, this yields: TC/sup 0/=PAC/sup 0/=C=AC/sup 0/. Another restatement of this characterization is that TC/sup 0/ can be simulated by constant-depth arithmetic circuits, with a single threshold gate. We hope that perhaps this characterization of TC/sup 0/ in terms of AC/sup 0/ circuits might provide a new avenue of attack for proving lower bounds. Our characterization differs markedly from earlier characterizations of TC/sup 0/ in terms of arithmetic circuits over finite fields. Using our model of arithmetic circuits, computation over finite fields yields ACC/sup 0/. We also prove a number of closure properties and normal forms for AC/sup 0/.

We show that in the context of nonuniform complexity, nondeterministic logarithmic space bounded computation can be made unambiguous. An analogous result holds for the class of problems reducible to context-free languages. In terms of complexity classes, this can be stated as: NL/poly=UL/poly LogCFL/poly=UAuxPDA(log n, n/sup O(1)/)/poly.

We prove that the Berman-Hartmanis isomorphism conjecturers true under ACO reductions.More generafly, we show three theorems that hold for any comdexitv class C closed under (uniform) TCO-commtable man~-one" reductions.Isomorp'hism:The sets c~mplete for Cunder ACO reductions are afl isomorphic under isomorphisms computable and invertible by ACO circuits of depth three.Ga : p The sets that are complete for C under ACO and NC reducibility coincide.Stop Gap: The sets that are complete for C under ACO[mod 2] and ACO reducibility do not coincide.(These theorems hold both in the non-uniform and P-uniform settings.) To prove the second theorem for P-uniform settings, we show how to derandomize a version of the switching lemma, which may be of independent interest.(We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.)

We show that for most complexity classes of interest, all sets complete under first-order projections (fops) are isomorphic under first-order isomorphisms. That is, a very restricted version of the Berman--Hartmanis conjecture holds. Since "natural" complete problems seem to stay complete via fops, this indicates that up to first-order isomorphism there is only one "natural" complete problem for each "nice" complexity class.

We show that all sets complete for NC/sup 1/ under AC/sup 0/ reductions are isomorphic under AC/sup 0/-computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC/sup 1/-computable many-one reductions, the sets complete for C under NC/sup 0/ reductions are all isomorphic under AC/sup 0/-computable isomorphisms. Our result showing that the complete degree for NC/sup 1/ collapses to an isomorphism type follows from a theorem showing that in NC/sup 1/, the complete degrees for AC/sup 0/ and NC/sup 0/ reducibility coincide. This theorem does not hold for strongly uniform reduction: we show that there are Dlogtime-uniform AC/sup 0/-complete sets for NC/sup 1/ that are not Dlogtime-uniform NC/sup 0/-complete.

ComplexityClasses for Counting and Enumeration

We present a notion of resource-bounded measure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause Lutz's definitions to apply only to classes at least as large as E. We present many of the basic properties of this measure, and use it to explore the class of sets that are hard for BPP. Bennett and Gill showed that almost all sets are hard for BPP; Lutz improved this from Lebesgue measure to measure on ESPACE. We use our measure to improve this still further, showing that for all /spl epsiv/>0, almost every set in E/sub /spl epsiv// is hard for BPP, where E/sub /spl epsiv//=/spl cup//sub /spl delta/>

The authors show that uniform families of ACC circuits of subexponential size cannot compute the permanent function. This also implies similar lower bounds for certain sets in PP This is one of the very few examples of a lower bound in circuit complexity whose proof hinges on the uniformity condition; it is still unknown if there is any set in ${\operatorname{Ntime}}(2^{n^{O(1)} } )$ that does not have nonuniform ACC circuits.

We show that for every family of arithmetic circuits of polynomial size and degree over the algebra (Z*, max, concat ), there is an equivalent family of arithmetic circuits of depth log2 n.(The depth can be reduced to log n if unbounded fan-in is allowed.)This is the first depth-reduction result for arithmetic circuits Olrer a nonco~utative semiring, and it complements the lower bounds of [Ni91,K090] showing that depth reduction cannot be done in the general noncommutative setting.The (max,concat) semiring is of interest, because it characterizes certain classes of optimization problems [AJ92, Vi91].In particular, our results show that OptSACi is contained in AC1.We also prove other results relating Boolean and arithmetic circuit complexity.We show that ACl has no more power than arithmetic circuits of polynomial size and degree n"(log log') (improving the trivial bound of nOIIOg')).Connections are drawn between TCl and arithmetic circuits of polynomial size and degree.

The low hierarchy in NP [27] and the extended low hierarchy [8] have been useful in

For various polynomial-time reducibilities r, this paper asks whether being r-reducible to a sparse set is a broader notion than being r-equivalent to a sparse set. Although distinguishing equivalence and reducibility to sparse sets, for many-one or 1-truth-table reductions, would imply that $P \ne NP$, this paper shows that for k-truth-table reductions, $k \geq 2$, equivalence and reducibility to sparse sets provably differ. Though Gavaldà and Watanabe have shown that, for any polynomial-time computable unbounded function $f( \cdot )$, some sets $f(n)$-truth-table reducible to sparse sets are not even Turing equivalent to sparse sets, this paper shows that extending their result to the 2-truth-table case would provide a proof that $P\ne NP$. Additionally, this paper studies the relative power of different notions of reducibility, and proves that disjunctive and conjunctive truth-table reductions to sparse sets are surprisingly powerful, refuting a conjecture of Ko.

The author presents a very simple proof of the fact that any language accepted by polynomial-size depth-k unbounded-fan-in circuits of AND and OR gates is accepted by depth-three threshold circuits of size n raised to the power O(log/sup k/n). The proof uses much of the intuition of S. Toda's result that the polynomial hierarchy is contained in P/sup Hash P/ (30th Ann. Symp. Foundations Comput. Sci., p.514-519, 1989).>

Much complexity-theoretic work on parallelism has focused on the class NC, which is defined in terms of logspace-uniform circuits. Yet P-uniform circuit complexity is in some ways a more natural setting for studying feasible parallelism. In this paper, P-uniform NC (PUNC) is characterized in terms of space-bounded AuxPDAs and alternating Turing Machines with bounded access to the input. The notions of general-purpose and special-purpose computation are considered, and a general-purpose parallel computer for PUNC is presented. It is also shown that NC = PUNC if all tally languages in P are in NC; this implies that the NC = PUNC question and the NC = P question are both instances of the ASPACE( S ( n )) = ASPACE,TIME( S ( n ), S ( n ) o (1) ) question. As a corollary, it follows that NC = PUNC implies PSPACE = DTIME(2 no (1) ).

P-printable sets arise naturally in the.studies of generalized Kolmogorov complexity and data compression, as well as in other areas. We present new characterizations of the P-printable sets and present necessary and sufficient conditions for the existence of sparse sets in P that are not P-printable. As a corollary to one of our results, we show that the class of sets of small generalized Kolmogorov complexity is exactly the class of sets which are P-isomorphic to a tally language.

If secure pseudorandom generators exist, then probabilistic computation does not uniformly speed up deterministic computation. If sets in P must contain infinitely many noncomplex strings, then nondeterministic computation does not uniformly speed up deterministic computation. Connections are drawn between pseudorandom generation, generalized Kolmogorov complexity, and immunity properties of complexity classes.