Search

We apply to Petri net theory the technique of polynomialtime many-one reductions. We study boundedness, reachability, deadlock, liveness problems and some of their variations. We derive three main results. Firstly, we highlight the power of expression of reachability which can polynomially give evidence of unboundedness. Secondly, we prove that reachability and deadlock are polynomially-time equivalent; this improves the known recursive reduction and it complements the result of Cheng and al. [4]. Moreover, we show the polynomial equivalence of liveness and t-liveness. Hence, we regroup the problems in three main classes: boundedness, reachability and liveness. Finally, we give an upper bound on the boundedness for post self-modified nets: \(2^{O(size(N)^2 *\log size(N))} \). This improves a decidability result of Valk [18].

We show that there is a set that is almost complete but not complete under polynomial-time many-one (p-m) reductions for the class E of sets computable in deterministic time 2lin. Here a set in a complexity class C is almost complete for C under some given reducibility if the class of the problems in C that do not reduce to this set has measure 0 in C in the sense of Lutz's resource-bounded measure theory. We also show that the almost complete sets for E under polynomial time-bounded length-increasing one–one reductions and truth-table reductions of norm 1 coincide with the almost p-m-complete sets for E. Moreover, we obtain similar results for the class EXP of sets computable in deterministic time 2poly.

We study the relation of autoreducibility and mitoticity for polylog-space many-one reductions and log-space many-one reductions. For polylog-space these notions coincide, while proving the same for log-space is out of reach. More precisely, we show the following results with respect to nontrivial sets and many-one reductions:1.polylog-space autoreducible ⇔ polylog-space mitotic,2.log-space mitotic ⇒ log-space autoreducible ⇒ (logn⋅loglogn)-space mitotic,3.relative to an oracle, log-space autoreducible ⇏ log-space mitotic. The oracle is an infinite family of graphs whose construction combines arguments from Ramsey theory and Kolmogorov complexity.

This paper investigates nondeterministic bounded query classes in relation to the complexity of NP-hard approximation problems and the Boolean Hierarchy. Nondeterministic bounded query classes turn out be rather suitable for describing the complexity of NP-hard approximation problems. The results in this paper take advantage of this machine-based model to prove that in many cases, NP-approximation problems have the upward collapse property. That is, a reduction between NP-approximation problems of apparently different complexity at a lower level results in a similar reduction at a higher level. For example, if MAXCLIQUE reduces to (log n)-approximating MAXCLIQUE using many–one reductions, then the Traveling Salesman Problem (TSP) is equivalent to MAXCLIQUE under many–one reductions. Several upward collapse theorems are presented in this paper. The proofs of these theorems rely heavily on the machinery provided by the nondeterministic bounded query classes. In fact, these results depend on a surprising connection between the Boolean hierarchy and nondeterministic bounded query classes.

Building on a recent breakthrough by Ogihara, we resolve a conjecture made by Hartmanis in 1978 regarding the (non)existence of sparse sets complete for P under logspace many–one reductions. We show that if there exists a sparse hard set for P under logspace many–one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many–one reductions computable in NC1, then P collapses to NC1.

This paper investigates the distribution and nonuniform complexity of problems that are complete or weakly complete for ESPACE under nonuniform many-one reductions that are computed by polynomial-size circuits (P/Poly-many-one reductions). Every weakly P/Poly-many-one-complete problem is shown to have a dense, exponential, nonuniform complexity core. An exponential lower bound on the space-bounded Kolmogorov complexities of weakly P/Poly-Turing-complete problems is established. More importantly, the P/Poly-many-one-complete problems are shown to be unusually simple elements of ESPACE, in the sense that they obey nontrivial upper bounds on nonuniform complexity (size of nonuniform complexity cores and space-bounded Kolmogorov complexity) that are violated by almost every element of ESPACE. More generally, a Small Span Theorem for P/Poly-many-one reducibility in ESPACE is proven and used to show that every P/Poly-many-one degree -including the complete degree — has measure 0 in ESPACE. (In contrast, almost every element of ESPACE is weakly P-many-one complete.) All upper and lower bounds are shown to be tight.

Let gamma be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in gamma is in Logspace or complete for the class CSP(gamma)_NP under deterministic polynomial-time many-one reductions. Here, CSP(gamma)_NP is the class of problems that can be reduced to the Constraint Satisfaction Problem of gamma under non-deterministic polynomial-time many-one reductions., Comment: 8 pages

Two sets are said to form a minimal pair for polynomial many-one reductions if neither set is in P and the only sets which are polynomially reducible (via polynomial many–one reductions) to both sets are in P. We consider the question of which complete sets can be the top (that is the supremum) of a minimal pair. Our main result is that any elementary recursive set which is hard for deterministic exponential time cannot be the top of a minimal pair. Hence in particular any complete set for an elementary recursive class containing exponential time cannot be such a supremum. For NP-complete sets the problem remains open. We show here that it is oracle dependent. This is the first example of an oracle dependent property which is completely degree theoretic.

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.

In this paper we study the consequences of the existence of sparse hard sets for different complexity classes under certain types of deterministic, randomized and nondeterministic reductions. We show that if an NP-complete set is bounded-truth-table reducible to a set that conjunctively reduces to a sparse set then P = NP. Relatedly, we show that if an NP-complete set is bounded-truth-table reducible to a set that co-rp reduces to some set that conjunctively reduces to a sparse set then RP = NP. We also prove similar results under the (apparently) weaker assumption that some solution of the promise problem (1-SAT,SAT) reduces via the mentioned reductions to a sparse set. Finally we consider nondeterministic polynomial time many-one reductions to sparse and co-sparse sets. We prove that if a co-NP-complete set reduces via a nondeterministic polynomial time many-one reduction to a co-sparse set then PH = Theta_2. On the other hand, we show that nondeterministic polynomial time many-one reductions to sparse sets are as powerful as nondeterministic Turing reductions to sparse sets.

Let Γ be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in Γ is in LOGSPACE or complete for the class CSP(Γ)NP under deterministic polynomial-time many-one reductions. Here, CSP(Γ)NP is the class of problems that can be reduced to the constraint satisfaction problem of Γ under non-deterministic polynomial-time many-one reductions.

We study the relation of autoreducibility and mitoticity for polylog-space many-one reductions and log-space many-one reductions. For polylog-space these notions coincide, while proving the same for log-space is out of reach. More precisely, we show the following results with respect to nontrivial sets and many-one reductions. 1 polylog-space autoreducible ${\,\mathop{\Leftrightarrow}\,}$ polylog-space mitotic 1 log-space mitotic log-space autoreducible (logn ·loglogn)-space mitotic 1 relative to an oracle, log-space autoreducible log-space mitotic The oracle is an infinite family of graphs whose construction combines arguments from Ramsey theory and Kolmogorov complexity.

Building on the recent breakthrough by M. Ogihara (1995), we resolve a conjecture made by J. Hartmanis (1978) regarding the (non) existence of sparse sets complete for P under logspace many-one reductions. We show that if there exists a sparse hard set for P under logspace many-one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many-one reductions computable in NC/sup 1/, then P collapses to NC/sup 1/.

J. Hartmanis (1978) conjectured that there exist no sparse complete sets for P under logspace many-one reductions. In this paper, in support of the conjecture, it is shown that if P has sparse hard sets under logspace many-one reductions, then P/spl sube/DSPACE[log/sup 2/n]. The result follows from a more general statement: if P has 2/sup polylog/ sparse hard sets under poly-logarithmic space-computable many-one reductions, then P/spl sube/DSPACE[polylog].

We investigate the computational complexity of some important problems in linear algebra. 1. The problem of verifying the characteristic polynomial of a matrix is known to be in the complexity class C/sub =/L (Exact Counting in Logspace). We show that it is complete for C/sub =/L under logspace many-one reductions. 2. The problem of deciding whether two matrices are similar is known to be in the complexity class AC/sup 0/(C=L). We show that it is complete for this class under logspace many-one reductions. We also consider the problems of deciding equivalence and congruence of matrices.

We investigate the computational complexity of the minimal polynomial of an integer matrix. We show that the computation of the minimal polynomial is in AC0(GapL), the AC0-closure of the logspace counting class GapL, which is contained in NC2. Our main result is that the problem is hard for GapL (under AC0 many-one reductions). The result extends to the verification of all invariant factors of an integer matrix. Furthermore, we consider the complexity to check whether an integer matrix is diagonalizable. We show that this problem lies in AC0(GapL) and is hard for AC0(C=L) (under AC0 many-one reductions).

This paper investigates the distribution and nonuniform complexity of problems that are complete or weakly complete for ESPACE under nonuniform many-one reductions that are computed by polynomial-size circuits (P/Poly-many-one reductions). Every weakly P/Poly-many-one-complete problem is shown to have a dense, exponential, nonuniform complexity core. An exponential lower bound on the space-bounded Kolmogorov complexities of weakly P/Poly-Turing-complete problems is established. More importantly, the P/Poly-many-one-complete problems are shown to be unusually simple elements of ESPACE, in the sense that they obey nontrivial upper bounds on nonuniform complexity (size of nonuniform complexity cores and space-bounded Kolmogorov complexity) that are violated by almost every element of ESPACE. More generally, a Small Span Theorem for P/Poly-many-one reducibility in ESPACE is proven and used to show that every P/Poly-many-one degree -including the complete degree — has measure 0 in ESPACE. (In contrast, almost every element of ESPACE is weakly P-many-one complete.) All upper and lower bounds are shown to be tight.

Inspired by the recent solution of the Berman-Hartmanis conjecture [SIAM J. Comp., 6 (1977), pp. 305–322] that NP cannot have a sparse complete set for many-one reductions unless ${\text{P}} = {\text{NP}}$, we analyze the implications of NP and PSPACE having sparse, hard or complete sets for reduction types more general than the many-one reductions. Three special cases of truth-table reductions are considered. First we show that if NP (PSPACE) has a tally $ \leqq _{k - T}^P $-hard set, then ${\text{P}} = {\text{NP}}$$({\text{P}} = {\text{PSPACE}})$. Here $ \leqq _{k - T}^P $ denotes a subcase of polynomial time Turing reducibility in which, for some constant k, the reducing Turing machine is allowed to make at most k queries to the oracle. We also show that if co-NP (PSPACE) has a sparse hard set for conjunctive polynomial time reductions, then ${\text{P}} = {\text{NP}}$$({\text{P}} = {\text{PSPACE}})$.

We define a new class of total search problems as a subclass of Megiddo and Papadimitriou’s class of total \({\mathsf {NP}}\) search problems, in which solutions are verifiable in \({\mathsf {AC}}^0\). We denote this class \(\forall \exists {\mathsf {AC}}^0\). We show that all total \({\mathsf {NP}}\) search problems are equivalent, w.r.t. \({\mathsf {AC}}^0\)-many-one reductions, to search problems in \(\forall \exists {\mathsf {AC}}^0\). Furthermore, we show that \(\forall \exists {\mathsf {AC}}^0\) contains well-known problems such as the Stable Marriage and the Maximal Independent Set problems. We introduce the class of Inflationary Iteration problems in \(\forall \exists {\mathsf {AC}}^0\), and show that it characterizes the provably total \({\mathsf {NP}}\) search problems of the bounded arithmetic theory corresponding to polynomial-time. Cook and Nguyen introduced a generic way of defining a bounded arithmetic theory \({\mathsf {VC}}\) for complexity classes \({\mathsf {C}}\) which can be obtained using a complete problem. For such C we will define a new class \({\mathsf {KPT[C]}}\) of \(\forall \exists {\mathsf {AC}}^0\) search problems based on Student-Teacher games in which the student has computing power limited to \({\mathsf {AC}}^0\). We prove that \({\mathsf {KPT[C]}}\) characterizes the provably total \({\mathsf {NP}}\) search problems of the bounded arithmetic theory corresponding to \({\mathsf {C}}\). All our characterizations are obtained via “new-style” witnessing theorems, where reductions are provable in a theory corresponding to AC \(^0\).

The Orbit problem is defined as follows: Given a matrix A?? n×n and vectors x,y?? n , does there exist a non-negative integer i such that A i x=y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4):808---821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C=L with respect to logspace many-one reductions.

Jones and Skyum in [J Sk 77], [J Sk 79], and [J Sk 81], as well as, van Leeuwen in [vL] and Sudborough in [Su77] classified the complexities of various problems concerning L systems. This was done by showing these problems, formulated as languages, to be complete for complexity classes like NSPACE(log n), DTIME(Poly), NTIME(Poly), or DSPACE(Poly) with respect to deterministic logarithmic space-bounded many-one reductions. The aim of this paper is to do the same for fixed membership problems of context-free L systems with respect to nondeterministic log-space bounded many-one reductions (see [Lan 84]).

We prove that the graph isomorphism problem restricted to trees and to colored graphs with color multiplicities 2 and 3 is many-one complete for several complexity classes within NC2. In particular we show that tree isomorphism, when trees are encoded as strings, is NC1-hard under AC0-reductions. NC1-completeness thus follows from Buss's NC1 upper bound. By contrast, we prove that testing isomorphism of two trees encoded as pointer lists is L-complete. Concerning colored graphs we show that the isomorphism problem for graphs with color multiplicities 2 and 3 is complete for symmetric logarithmic space SL under many-one reductions. This result improves the existing upper bounds for the problem. We also show that the graph automorphism problem for colored graphs with color classes of size 2 is equivalent to deciding whether a graph has more than a single connected component and we prove that for color classes of size 3 the graph automorphism problem is contained in SL.

We build on the recent progress regarding isomorphisms of complete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC0 reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC0 circuits. One of the main tools in proving the isomorphism theorem in Agrawal et al. (1998) is a “Gap Theorem”, showing that all sets complete under AC0 reductions are in fact already complete under NC0 reductions. The following questions were left open in that paper:¶1. Does the “gap” between NC0 and AC0 extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC0reductions?¶2. Does a uniform version of the isomorphism theorem hold?¶3. Is depth-three optimal, or are the complete sets isomorphic under isomorphisms computable by depth-two circuits?¶We answer all of these questions. In particular, we prove that the Berman—Hartmanis isomorphism conjecture is true for P-uniform AC0 reductions. More precisely, we show that for any class $ {\cal C} $ closed under uniform TC0-computable many-one reductions, the following three theorems hold:¶1. If $ {\cal C} $ contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC0[mod 2] reductions, then there are such sets that are not complete under (even non-uniform) AC0 reductions.¶2. The sets complete for $ {\cal C} $ under P-uniform AC0 reductions are all isomorphic under isomorphisms computable and invertible by P-uniform AC0circuits of depth-three.¶3. There are sets complete for $ {\cal C} $ under Dlogtime-uniform AC0 reductions that are not isomorphic under any isomorphism computed by (even non-uniform) AC0 circuits of depth two.¶To prove the second theorem, 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 approximating the shortest vector problem (in any $\ell_p$ norm) to within any constant factor less than $\sqrt[p]2$ is hard for NP under reverse unfaithful random reductions with inverse polynomial error probability. In particular, approximating the shortest vector problem is not in RP (random polynomial time), unless NP equals RP. We also prove a proper NP-hardness result (i.e., hardness under deterministic many-one reductions) under a reasonable number theoretic conjecture on the distribution of square-free smooth numbers. As part of our proof, we give an alternative construction of Ajtai's constructive variant of Sauer's lemma that greatly simplifies Ajtai's original proof.

We resolve a conjecture of Hartmanis from 1978 about sparse hard sets for nondeterministic logspace (NL). We show that there exists a sparse hard set S for NL under logspace many-one reductions if and only if NL=L (deterministic logspace).

The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions, one of them is the Boolean isomorphism relation. Most of these computational problems turn out to be between co-NP and $\Sigma$ p 2 .

We give a simplified proof of a theorem of Lagarias, Lenstra and Schnorr [17] that the problem of approximating the length of the shortest lattice vector within a factor of Cn, for an appropriate constant C, cannot be NP-hard, unless NP = coNP. We also prove that the problem of finding a n 1 4 - unique shortest lattice vector is not NP-hard under polynomial time many-one reductions, unless the polynomial time hierarchy collapses. © 1998—Elsevier Science B.V. All rights reserved

We propose an extension of the framework for discussing the computational complexity of problems involving uncountably many objects, such as real numbers, sets and functions, that can be represented only through approximation. The key idea is to use (a certain class of) string functions as names representing these objects. These are more expressive than infinite sequences, which served as names in prior work that formulated complexity in more restricted settings. An advantage of using string functions is that we can define their "size" in the way inspired by higher-type complexity theory. This enables us to talk about computation on string functions whose time or space is bounded polynomially in the input size, giving rise to more general analogues of the classes P, NP, and PSPACE. We also define NP- and PSPACE-completeness under suitable many-one reductions. Because our framework separates machine computation and semantics, it can be applied to problems on sets of interest in analysis once we specify a suitable representation (encoding). As prototype applications, we consider the complexity of functions (operators) on real numbers, real sets, and real functions. For example, the task of numerical algorithms for solving a certain class of differential equations is naturally viewed as an operator taking real functions to real functions. As there was no complexity theory for operators, previous results only stated how complex the solution can be. We now reformulate them and show that the operator itself is polynomial-space complete., 22 pages, 9 figures; a few typos fixed after journal publication

Polynomial-time many-one reductions provide the standard notion of completeness for complexity classes. However, as first explicated by Berman and Hartmanis in their work on the isomorphism conjecture, all natural complete problems are actually complete under reductions with stronger properties. We study the length-increasing property and show under various computational hardness assumptions that all PSPACE-complete problems are complete via length-increasing reductions that are computable with a small amount of nonuniform advice.

This paper takes a new approach to studying the NP-isomorphism problem initiated by Berman and Hartmanis. We consider polynomial-time computable and invertible bijections among NP-complete sets that preserve the underlying natural distributions on random instances. We show that there are natural NP-complete problems which are not polynomially isomorphic when instances are chosen at random because no polynomial-time isomorphisms can preserve the underlying natural distributions on instances of these problems, On the other hand, we show that all the known average-case NP-complete problems under many-one reductions are polynomially isomorphic with respect to their distributions on random instances. Simple and accessible proofs to the known average-case NP-complete problems are presented when establishing the isomorphism result. New average-case NP-complete problems are also presented.

A dichotomy theorem for counting problems due to Creignou and Hermann states that or any finite set S of logical relations, the counting problem #SAT(S) is either in FP, or #P-complete. In the present paper we show a dichotomy theorem for polynomial evaluation. That is, we show that for a given set S, either there exists a VNP-complete family of polynomials associated to S, or the associated families of polynomials are all in VP. We give a concise characterization of the sets S that give rise to "easy" and "hard" polynomials. We also prove that several problems which were known to be # P-complete under Turing reductions only are in fact # P-complete under many-one reductions.

A tournament is a graph in which each pair of distinct vertices is connected by exactly one directed edge. Tournaments are an important graph class, for which isomorphism testing seems to be easier to compute than for the isomorphism problem of general graphs. We show that tournament isomorphism and tournament automorphism is hard under DLOGTIME uniform AC0 many-one reductions for the complexity classes NL, C=L, PL (probabilistic logarithmic space), for logarithmic space modular counting classes ModkL with odd k = 3 and for DET, the class of problems, NC1 reducible to the determinant. These lower bounds have been proven for graph isomorphism, see [21].

We study the approximability of Max Ones when the number of variable occurrences is bounded by a constant. For conservative constraint languages (i.e., when the unary relations are included) we give a complete classification when the number of occurrences is three or more and a partial classification when the bound is two. For the non-conservative case we prove that it is either trivial or equivalent to the corresponding conservative problem under polynomial-time many-one reductions.

Let χ(G) denote the chromatic number of a graph G. A colored set of vertices of G is called forcing if its coloring is extendable to a proper χ(G)-coloring of the whole graph in a unique way. The forcing chromatic number Fχ(G) is the smallest cardinality of a forcing set of G. We estimate the computational complexity of Fχ(G) relating it to the complexity class US introduced by Blass and Gurevich. We prove that recognizing if Fχ(G) ≤ 2 is US-hard with respect to polynomial-time many-one reductions. Furthermore, this problem is coNP-hard even under the promises that Fχ(G) ≤ 3 and G is 3-chromatic. On the other hand, recognizing if Fχ(G) ≤ k, for each constant k, is reducible to a problem in US via a disjunctive truth-table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph.

We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is $s$-chromatic if it is colorable in $s$ colors and any coloring of it uses at least $s$ colors. The forcing chromatic number $F(G)$ of an $s$-chromatic graph $G$ is the smallest number of vertices which must be colored so that, with the restriction that $s$ colors are used, every remaining vertex has its color determined uniquely. We estimate the computational complexity of $F(G)$ relating it to the complexity class US introduced by Blass and Gurevich. We prove that recognizing if $F(G)\le 2$ is US-hard with respect to polynomial-time many-one reductions. Moreover, this problem is coNP-hard even under the promises that $F(G)\le 3$ and $G$ is 3-chromatic. On the other hand, recognizing if $F(G)\le k$, for each constant $k$, is reducible to a problem in US via disjunctive truth-table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph., 24 pages; This is the final version

It is shown that for recursively enumerable sets, p-creativeness and p-complete creativeness are equivalent, and Myhill's theorem still holds in the polynomial setting. For P (NP), p-creativeness is shown to be equivalent to p-complete creativeness. The existence of p-creative sets for P (NP) in EXP (NEXP) is given. Moreover, it is shown that every p-m-complete set for EXP (NEXP) is p-completely creative for P (NP), and every p-creative set for NP is NP-hard via many-one reductions. Other results for k-completely creative sets are obtained. >

Structures of polynomial-time computable distributions and polynomial-time many-one reductions on randomized decision problems are investigated. The scope is widened from the most studied class DNP (distributional-NP) to the class ANP (average-NP), which consists of randomized decision problems accepted by nondeterministic Turing machines in average polynomial time. Results indicate that the structures of average-case complexity classes are very different from their counterparts in worst-case complexity due to the complex structures of probability distributions and distribution functions. >

Polynomial isomorphisms are defined for NP-complete sets on random instances. Not only are polynomial-time computable and invertible bijections among complete sets considered, but also it is required that these bijections preserve distributions on random instances of these sets. Sufficient conditions for randomized decision problems to be polynomially isomorphic are shown. It is then proved that all the known average-case NP-complete problems under many-one reductions are polynomially isomorphic. These problems include the randomized tiling problem, the randomized halting problem, the randomized Post correspondence problem, and the randomized word problem for Thue systems. >

It is shown that, by choosing appropriate encodings of instances as relational structures, several known polynomial-time many-one reductions can he described in first-order logic, and furthermore they are monadic. As a corollary, several known NP-complete problems in monadic NP are shown not to be in monadic co-NP. It is further shown that there is no monadic first-order reduction from connectivity to directed reachability, even in the presence of successor. Finally, some classes of syntactically restricted first-order reductions are shown to be incomparable. >

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.

We show that the graph isomorphism problem is hard under DLOGTIME uniform AC{$^0$} many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class {Mod}$_k$L and for the class DET of problems NC{$^1$} reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem.

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 prove that the graph isomorphism problem restricted to colored graphs with color multiplicities 2 and 3 is complete for symmetric logarithmic space SL under many-one reductions. This result improves the existing upper bounds for the problem.We also show that the graph automorphism problem for colored graphs with color classes of size 2 is equivalent to deciding whether an undirected graph has more than a single connected component and we prove that for color classes of size 3 the graph automorphism problem is contained in SL.

This paper investigates the instance complexities of problems that are hard or weakly hard for exponential time under polynomial time, many-one reductions. It is shown that almost every instance of almost every problem in exponential time has essentially maximal instance complexity. It follows that every weakly hard problem has a dense set of such maximally hard instances. This extends the theorem, due to Orponen, Ko, Schoning and Watanabe (1994), that every hard problem for exponential time has a dense set of maximally hard instances. Complementing this, it is shown that every hard problem for exponential time also has a dense set of unusually easy instances.

We construct an oracle A such that PA = PA and NPA = EXPA: This relativized world has several amazing properties: The oracle A gives the first relativized world where one can solve satisfiability on formulae with at most one assignment yet P 6= NP. The oracle A is the first where PA = UPA 6= NPA = coNPA: The construction gives a much simpler proof than that of Fenner, Fortnow and Kurtz of a relativized world where all the NP-complete sets are polynomial-time isomorphic. It is the first such computable oracle. Relative to A we have a collapse of EXPA ZPPA PA/poly. We also create a different relativized world where there exists a set L in NP that is NP-complete under reductions that make one query to L but not complete under traditional many-one reductions. This contrasts with the result of Buhrman, Spaan and Torenvliet showing that these two completeness notions for NEXP coincide. Research done at Yale and the University of Maryland. Address: Elect Eng Comp Science, 19 Memorial Dr W Ste 2, Bethlehem PA 180153084, USA. Supported in part by the National Science Foundation under grants CCR-8958528, CCR-9415410 and CCR-9700417 and by NASA under grant NAG 52895. Email: beigel@eecs.lehigh.edu. http://www.eecs.lehigh.edu/ beigel/ xAddress: CWI, Kruislaan 413, 1098SJ Amsterdam, The Netherlands. Partially supported by the Dutch foundation for scientific research (NWO) by SION project 612-34-002, and by the European Union through NeuroCOLT ESPRIT Working Group Nr. 8556, and HC&M grant nr. ERB4050PL93-0516. Email: buhrman@cwi.nl. http://www.cwi.nl/ buhrman/ {Research done while on leave at CWI. Address: University of Chicago, Department of Computer Science, 1100 E. 58th. St., Chicago, IL 60637, USA. Supported in part by NSF grant CCR 92-53582, the Dutch Foundation for Scientific Research (NWO) and a Fulbright Scholar award. Email: fortnow@cs.uchicago.edu. http://www.cs.uchicago.edu/ fortnow

We resolve a conjecture of Hartmanis from 1978 about sparse hard sets for nondeterministic logspace (NL). We show that there exists a sparse hard set S for NL under logspace many-one reductions if and only if NL = L (deterministic logspace).

1 Time, Hardware, and Uniformity.- 1 Introduction.- 2 Background: Descriptive Complexity.- 3 First Uniformity Theorem.- 4 Variables That Are Longer Than log nBits.- 5 Uniformity: The Third Dimension.- 6 Variables That Are Shorter Than log nBits.- 7 Conclusions.- 2 Quantum Computation.- 1 The Need for Quantum Mechanics.- 2 Basic Principles of Quantum Mechanics.- 2.1 Probability Amplitudes.- 2.2 Qubits and How to Observe Them.- 2.3 Digression on Quantum Cryptography.- 2.4 Evolution of a Quantum System.- 2.5 Quantum Registers.- 3 Computing with Quantum Registers.- 4 Separating Two Classes of Functions.- 5 Shor's Factoring Algorithm.- 6 Building a Quantum Computer.- 3 Sparse Sets versus Complexity Classes.- 1 Introduction.- 2 Earlier Results for Turing Reductions.- 2.1 Sparse Sets and Polynomial Size Circuits.- 2.2 The Karp-Lipton Theorem.- 2.3 Long's Extension.- 3 Earlier Results for Many-One Reductions.- 3.1 The Isomorphism Conjecture for NP.- 3.2 Mahaney's Theorem.- 4 Bounded Truth Table Reduction of NP.- 4.1 Extensions.- 5 The Hartmanis Conjecture for P.- 5.1 Ogihara's Language and Randomized NC2.- 5.2 Deterministic Construction.- 5.3 The Finale: NC1 Simulation.- 6 Conclusions.- 4 Counting Complexity.- 1 Introduction.- 2 Preliminaries.- 3 Counting Functions.- 3.1 Algebraic Properties of Counting Functions.- 3.2 A Randomized sign Function.- 3.3 Counting Functions and the Polynomial-Time Hierarchy.- 4 Counting Classes.- 4.1 Classifying Counting Classes.- 4.2 Counting Operators.- 4.3 The Polynomial-Time Hierarchy.- 4.4 Closure Properties of PP.- 5 Relativization.- 6 Other Work.- 6.1 Circuits.- 6.2 Lowness.- 6.3 Characterizing Specific Problems.- 6.4 Interactive Proof Systems.- 6.5 Counting in Space Classes.- 6.6 Other Research.- 5 A Taxonomy of Proof Systems.- 1 Introduction.- 2 A Technical Exposition.- 2.1 Interactive Proof Systems.- 2.2 MIP and PCP.- 2.3 Computationally Sound Proof Systems.- 2.4 Other Types of Proof Systems.- 2.5 Comparison.- 3 The Story.- 3.1 The Evolution of Proof Systems.- 3.2 PCP and Approximation.- 3.3 Interactive Proofs and Program Checking.- 3.4 Zero-Knowledge Proofs.- 6 Structural Properties of Complete Problems for Exponential Time.- 1 Introduction.- 2 Strong Reductions to Complete Sets.- 3 Immunity for Complete Problems.- 4 Differences between Complete Sets.- 5 Other Properties and Open Problems.- 5.1 Properties of "Weak" Complete Sets.- 5.2 Polynomial-Time Complete Recursively Enumerable Sets.- 5.3 A Short List of Open Problems.- 7 The Complexity of Obtaining Solutions for Problems in NP and NL.- 1 Introduction.- 2 Computing Optimal Solutions: The Class FPNP.- 3 Bounded Queries to NP.- 4 Computing Solutions Uniquely: The Class NPSV.- 5 Nonadaptive Queries to NP: The Class FPNPtt.- 6 A Look inside Nondeterministic Logspace.- 7 Conclusions.- 8 Biological Computing.- 1 Introduction.- 2 The One-Molecule Processor.- 3 A Brief Introduction to Biochemistry.- 3.1 DNA, RNA, and Proteins.- 3.2 Protein Synthesis.- 4 Computational Molecules.- 4.1 CNA.- 4.2 tCNA.- 4.3 The Synthesis of tCNA.- 5 The Microarchitecture of CNA Computers.- 6 A Brief Discussion of Adleman's Model Versus Our Model.- 7 Conclusions.- 9 Computing with Sublogarithmic Space.- 1 Are Sublogarithmic Space Classes of Any Interest?.- 2 The Alternating Sublogarithmic Space World.- 3 Adding Randomness.- 4 Special Limitations of Machines with a Sublogarithmic Space Bound.- 4.1 Technical Preliminaries.- 4.2 Inputs with a Periodic Structure.- 4.3 Fooling ATMs.- 5 A Survey of Lower Space Bound Proofs.- 5.1 Languages for Separating the Levels of the Alternation Hierarchy.- 5.2 ATMs with a Constant Number of Alternations.- 5.3 Unbounded Alternation.- 5.4 Closure Properties.- 5.5 Lower Bounds for Context-Free Languages.- 6 Conclusions and Open Problems.- 10 The Quantitative Structure of Exponential Time.- 1 Introduction.- 2 Preliminaries.- 3 Resource-Bounded Measure.- 4 Incompressibility and Bi-Immunity.- 5 Complexity Cores.- 6 Small Span Theorems.- 7 Weakly Hard Problems.- 8 Upper Bounds for Hard Problems.- 9 Nonuniform Complexity, Natural Proofs, and Pseudorandom Generators.- 10 Weak Stochasticity.- 11 Density of Hard Languages.- 12 Strong Hypotheses.- 13 Conclusions and Open Directions.- 11 Polynomials and Combinatorial Definitions of Languages.- 1 Introduction.- 2 Polynomials.- 3 Representation Schemes and Language Classes.- 4 Strong versus Weak Representation.- 5 Known Upper and Lower Bounds on Degree.- 6 Polynomials for Closure Properties.- 7 Probabilistic Polynomials.- 8 Other Combinatorial Structures.- 12 Average-Case Computational Complexity Theory.- 1 Introduction.- 2 Average Polynomial Time.- 3 Average-Case Completeness.- 3.1 Polynomial-Time Reductions.- 3.2 Polynomial-Time Computable Distributions.- 3.3 Uniform Distributions.- 3.4 Distribution Controlling Lemma.- 3.5 Distributional NP-Completeness.- 3.6 Average Polynomial-Time Reductions.- 3.7 Distributional Search Problems.- 4 Randomization.- 4.1 Flat Distributions and Incompleteness.- 4.2 Randomized Average Polynomial Time.- 4.3 Randomizing Reductions and Completeness.- 4.4 Polynomial-Time Sampling.- 4.5 Randomized Turing Reductions.- 5 Hierarchies of Average-Case Complexity.- 5.1 Average-Time Hierarchies.- 5.2 Fast Convergence of Average Time.- 5.3 Averaging on Ranking of Distributions.- 6 A Brief Survey of Other Results.

Recently a 1978 conjecture by Hartmanis was resolved by Cai and Sivakumar, following progress made by Ogihara. It was shown that there is no sparse set that is hard for P under logspace many-one reductions, unless P=LOGSPACE. We extend these results to the case of sparse sets that are hard under more general reducibilities. Furthermore, the proof technique can be applied to resolve open questions about hard sparse sets for NP as well. Using algebraic and probabilistic techniques, we show the following results.

Gap-definability and the gap-closure operator were defined in [FFK91]. Few complexity classes were known at that time to be gap-definable. In this paper, we give simple characterizations of both gap-definability and the gap-closure operator, and we show that many complexity classes are gap-definable, including P#P, \(P^{\# P_{[1]} }\), PSPACE, EXP, NEXP, MP, and BP·⊕P. If a class is closed under union, intersection and contains λ and Σ*, then it is gap-definable if and only if it contains SPP; its gap-closure is the closure of this class together with SPP under union and intersection. On the other hand, we give some examples of classes which are reasonable gap-definable but not closed under union (resp. intersection, complement). Finally, we show that a complexity class such as PP or PSPACE, if it is not equal to SPP, contains a maximal proper gap-definable subclass which is closed under many-one reductions.

This paper introduces a technique of relativizing already relativized computations and gives two interesting applications. The techniques developed here are simpler than the usual methods for constructing oracles that satisfy several requirements simultaneously. The first application shows that a result of Karp and Lipton (if sets in NP are decidable with polynomial-size circuits, then Σ P 2 = Π P 2 ) cannot be strengthened in the presence of certain oracles. This means that relativizable proof techniques cannot strengthen the conclusion to, say, P = NP . Such a stronger conclusion would be desirable as it would establish the equivalence of polynomial-time programs and polynomial-size circuits for solving NP-complete problems and would extend the known equivalence of polynomial-time programs and programs that are allowed a single query to a polynomial-size table. The second application gives an oracle C for which P C ≠ (NP C ∩ coNP C ) ≠ NP C and NP C ∩ coNP C has complete sets under polynomial-time many-one reductions. This complements a result of Sipser in which an oracle B is constructed for which NP B ∩ coNP B has no complete sets. These results suggest that current proof methods will not settle whether NP ∩ coNP has complete sets.