We introduce multi-head finite-state dimension, a generalization of finite-state dimension in which a group of finite-state agents (the heads) with oblivious, one-way movement rules, each reporting only one symbol at a time, enable their leader to bet on subsequent symbols in an infinite data stream. In aggregate, such a scheme constitutes an $h$-head finite state gambler whose maximum achievable growth rate of capital in this task, quantified using betting strategies called gales, determines the multi-head finite-state dimension of the sequence. The 1-head case is equivalent to finite-state dimension as defined by Dai, Lathrop, Lutz and Mayordomo (2004). In our main theorem, we prove a strict hierarchy as the number of heads increases, giving an explicit sequence family that separates, for each positive integer $h$, the earning power of $h$-head finite-state gamblers from that of $(h+1)$-head finite-state gamblers. We prove that multi-head finite-state dimension is stable under finite unions but that the corresponding quantity for any fixed number $h>1$ of heads--the $h$-head finite-state predimension--lacks this stability property.

Finite-state dimension, introduced early in this century as a finite-state version of classical Hausdorff dimension, is a quantitative measure of the lower asymptotic density of information in an infinite sequence over a finite alphabet, as perceived by finite automata. Finite-state dimension is a robust concept that now has equivalent formulations in terms of finite-state gambling, lossless finite-state data compression, finite-state prediction, entropy rates, and automatic Kolmogorov complexity. The 1972 Schnorr-Stimm dichotomy theorem gave the first automata-theoretic characterization of normal sequences, which had been studied in analytic number theory since Borel defined them in 1909. This theorem implies, in present-day terminology, that a sequence (or a real number having this sequence as its base-b expansion) is normal if and only if it has finite-state dimension 1. One of the most powerful classical tools for investigating normal numbers is the 1916 Weyl’s criterion, which characterizes normality in terms of exponential sums. Such sums are well studied objects with many connections to other aspects of analytic number theory, and this has made use of Weyl’s criterion especially fruitful. This raises the question whether Weyl’s criterion can be generalized from finite-state dimension 1 to arbitrary finite-state dimensions, thereby making it a quantitative tool for studying data compression, prediction, etc. i.e., Can we characterize all compression ratios using exponential sums?. This paper does exactly this. We extend Weyl’s criterion from a characterization of sequences with finite-state dimension 1 to a criterion that characterizes every finite-state dimension. This turns out not to be a routine generalization of the original Weyl criterion. Even though exponential sums may diverge for non-normal numbers, finite-state dimension can be characterized in terms of the dimensions of the subsequence limits of the exponential sums. In case the exponential sums are convergent, they converge to the Fourier coefficients of a probability measure whose dimension is precisely the finite-state dimension of the sequence. This new and surprising connection helps us bring Fourier analytic techniques to bear in proofs in finite-state dimension, yielding a new perspective. We demonstrate the utility of our criterion by substantially improving known results about preservation of finite-state dimension under arithmetic. We strictly generalize the results by Aistleitner and Doty, Lutz and Nandakumar for finite-state dimensions under arithmetic operations. We use the method of exponential sums and our Weyl criterion to obtain the following new result: If y is a number having finite-state strong dimension 0, then dim_FS(x+qy) = dim_FS(x) and Dim_FS(x+qy) = Dim_FS(x) for any x ∈ ℝ and q ∈ ℚ. This generalization uses recent estimates obtained in the work of Hochman [Hochman, 2014] regarding the entropy of convolutions of probability measures.

The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces Rn. These are classical questions, meaning that their statements do not involve computation or related aspects of logic. In this paper we extend the reach of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces X. We first extend two algorithmic dimensions—computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions dim⁡(x) and Dim(x) to individual points x∈X—to arbitrary separable metric spaces and to arbitrary gauge families. Our first two main results then extend the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families. We demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces. (For a concrete computational example, the stages E0,E1,E2,… used to construct a self-similar fractal E in the plane are elements of the hyperspace of the plane, and they converge to E in the hyperspace.) Our third main result, proven via our extended point-to-set principle, states that, under a wide variety of gauge families, the classical packing dimension agrees with the classical upper Minkowski dimension on all hyperspaces of compact sets. We use this theorem to give, for all sets E that are analytic, i.e., Σ11, a tight bound on the packing dimension of the hyperspace of E in terms of the packing dimension of E itself.

The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces ℝⁿ. These are classical questions, meaning that their statements do not involve computation or related aspects of logic. In this paper we extend the reach of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces X. We first extend two fractal dimensions—computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions dim(x) and Dim(x) to individual points x ∈ X—to arbitrary separable metric spaces and to arbitrary gauge families. Our first two main results then extend the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families. We demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces. (For a concrete computational example, the stages E₀, E₁, E₂, … used to construct a self-similar fractal E in the plane are elements of the hyperspace of the plane, and they converge to E in the hyperspace.) Our third main result, proven via our extended point-to-set principle, states that, under a wide variety of gauge families, the classical packing dimension agrees with the classical upper Minkowski dimension on all hyperspaces of compact sets. We use this theorem to give, for all sets E that are analytic, i.e., Σ¹₁, a tight bound on the packing dimension of the hyperspace of E in terms of the packing dimension of E itself.

A real number x is absolutely normal if, for every base b≥2, every two equally long strings of digits appear with equal asymptotic frequency in the base-b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x, with the nth bit of x appearing after npolylog(n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.

The Schnorr-Stimm dichotomy theorem (Schnorr and Stimm, 1972) concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S, the following two things are true. (1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S. (2) If S is normal, then any finite-state gambler loses money at an exponential rate betting on S. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence div(S||α) of a probability measure α on Σ from a sequence S over Σ and the upper asymptotic divergence Div(S||α) of α from S in such a way that a sequence S is α-normal (meaning that every string w has asymptotic frequency α(w) in S) if and only if Div(S||α)=0. We also use the Kullback-Leibler divergence to quantify the total risk RiskG(w) that a finite-state gambler G takes when betting along a prefix w of S. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to α-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes w of S. ( $1~'$ ) The infinitely-often exponential rate of winning in 1 is 2Div(S||α)|w|. ( $2~'$ ) The exponential rate of loss in 2 is 2- RiskG(w). We also use (1 $'$ ) to show that 1- Div(S||α)/c, where c = log(1/ mina ∈ Σα(a)), is an upper bound on the finite-state α-dimension of S and prove the dual fact that 1- div(S||α)/c is an upper bound on the finite-state strong α-dimension of S.

We show that very simple molecular systems, modeled as chemical reaction networks, can have behaviors that exhibit dramatic phase transitions at certain population thresholds. Moreover, the magnitudes of these thresholds can thwart attempts to use simulation, model checking, or approximation by differential equations to formally verify the behaviors of such systems at realistic populations. We show how formal theorem provers can successfully verify some such systems at populations where other verification methods fail.

The Schnorr-Stimm dichotomy theorem [Schnorr and Stimm, 1972] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S, the following two things are true. (1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S. (2) If S is normal, then any finite-state gambler betting on S loses money at an exponential rate betting on S. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence div(S||α) of a probability measure α on Σ from a sequence S over Σ and the upper asymptotic divergence Div(S||α) of α from S in such a way that a sequence S is α-normal (meaning that every string w has asymptotic frequency α(w) in S) if and only if Div(S||α)=0. We also use the Kullback-Leibler divergence to quantify the total risk Risk_G(w) that a finite-state gambler G takes when betting along a prefix w of S. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to α-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes w of S. (1') The infinitely-often exponential rate of winning in 1 is 2^{Div(S||α)|w|}. (2') The exponential rate of loss in 2 is 2^{-Risk_G(w)}. We also use (1') to show that 1-Div(S||α)/c, where c= log(1/ min_{a∈Σ} α(a)), is an upper bound on the finite-state α-dimension of S and prove the dual fact that 1-div(S||α)/c is an upper bound on the finite-state strong α-dimension of S.

Molecular programming uses the computational power of DNA and other biomolecules to create useful nanoscale systems. Molecular program applications being developed include medical sensors that can be absorbed by the body after use, drug capsules that open only when they find diseased cells, and programmable nanoscale robots. This tutorial introduces the model-based language commonly used to write the requirements for molecular programs. This high-level modeling language is mathematically simple, very general, and well documented. Importantly, specifications written in it can be automatically compiled into implementable, detailed design descriptions. Participants will leave knowing how to write the requirements for some small molecular system components, where to go to learn more, and what are some open problems for writing the requirements of large molecular programs.

Dynamic systems in DNA nanotechnology are often programmed using a chemical reaction network (CRN) model as an intermediate level of abstraction. In this paper, we design and analyze a CRN model of a watchdog timer, a device commonly used to monitor the health of a safety critical system. Our process uses incremental design practices with goal-oriented requirements engineering, software verification tools, and custom software to help automate the software engineering process. The watchdog timer is comprised of three components: an absence detector, a threshold filter, and a signal amplifier. These components are separately designed and verified, and only then composed to create the molecular watchdog timer. During the requirements-design iterations, simulation, model checking, and analysis are used to verify the system. Using this methodology several incomplete requirements and design flaws were found, and the final verified model helped determine specific parameters for biological experiments.

We prove that the abstract Tile Assembly Model (aTAM) of nanoscale self-assembly is intrinsically universal. This means that there is a single tile assembly system U that, with proper initialization, simulates any tile assembly system T. The simulation is "intrinsic" in the sense that the self-assembly process carried out by U is exactly that carried out by T, with each tile of T represented by an m × m "super tile" of U. Our construction works for the full aTAM at any temperature, and it faithfully simulates the deterministic or nondeterministic behavior of each T. Our construction succeeds by solving an analog of the cell differentiation problem in developmental biology: Each super tile of U, starting with those in the seed assembly, carries the "genome" of the simulated system T. At each location of a potential super tile in the self-assembly of U, a decision is made whether and how to express this genome, i.e., whether to generate a super tile and, if so, which tile of T it will represent. This decision must be achieved using asynchronous communication under incomplete information, but it achieves the correct global outcome(s).

We propose an extension of van Lamsweerde's goal-oriented requirements engineering to the domain of programmable DNA nanotechnology. This is a domain in which individual devices (agents) are at most a few dozen nanometers in diameter. These devices are programmed to assemble themselves from molecular components and perform their assigned tasks. The devices carry out their tasks in the probabilistic world of chemical kinetics, so they are individually error-prone. However, the number of devices deployed is roughly on the order of a nanomole (a 6 followed by fourteen 0s), and some goals are achieved when enough of these agents achieve their assigned subgoals. We show that it is useful in this setting to augment the AND/OR goal diagrams to allow goal refinements that are mediated by threshold functions, rather than ANDs or ORs. We illustrate this method by engineering requirements for a system of molecular detectors (DNA origami “pliers” that capture target molecules) invented by Kuzuya, Sakai, Yamazaki, Xu, and Komiyama (2011). We model this system in the Prism probabilistic symbolic model checker, and we use Prism to verify that requirements are satisfied, provided that the ratio of target molecules to detectors is neither too high nor too low. This gives prima facie evidence that software engineering methods can be used to make DNA nanotechnology more productive, predictable and safe.

DNA nanotechnology uses the information processing capabilities of nucleic acids to design self-assembling, programmable structures and devices at the nanoscale. Devices developed to date have been programmed to implement logic circuits and neural networks, capture or release specific molecules, and traverse molecular tracks and mazes. Here we investigate the use of requirements engineering methods to make DNA nanotechnology more productive, predictable, and safe. We use goal-oriented requirements modeling to identify, specify, and analyze a product family of DNA nanodevices, and we use PRISM model checking to verify both common properties across the family and properties that are specific to individual products. Challenges to doing requirements engineering in this domain include the error-prone nature of nanodevices carrying out their tasks in the probabilistic world of chemical kinetics, the fact that roughly a nanomole (a 1 followed by 14 0s) of devices are typically deployed at once, and the difficulty of specifying and achieving modularity in a realm where devices have many opportunities to interfere with each other. Nevertheless, our results show that requirements engineering is useful in DNA nanotechnology and that leveraging the similarities among nanodevices in the product family improves the modeling and analysis by supporting reuse.

We show that the Tile Assembly Model exhibits a strong notion of universality where the goal is to give a single tile assembly system that simulates the behavior of any other tile assembly system. We give a tile assembly system that is capable of simulating a very wide class of tile systems, including itself. Specifically, we give a tile set that simulates the assembly of any tile assembly system in a class of systems that we call \emph{locally consistent}: each tile binds with exactly the strength needed to stay attached, and that there are no glue mismatches between tiles in any produced assembly. Our construction is reminiscent of the studies of \emph{intrinsic universality} of cellular automata by Ollinger and others, in the sense that our simulation of a tile system $T$ by a tile system $U$ represents each tile in an assembly produced by $T$ by a $c \times c$ block of tiles in $U$, where $c$ is a constant depending on $T$ but not on the size of the assembly $T$ produces (which may in fact be infinite). Also, our construction improves on earlier simulations of tile assembly systems by other tile assembly systems (in particular, those of Soloveichik and Winfree, and of Demaine et al.) in that we simulate the actual process of self-assembly, not just the end result, as in Soloveichik and Winfree's construction, and we do not discriminate against infinite structures. Both previous results simulate only temperature 1 systems, whereas our construction simulates tile assembly systems operating at temperature 2.

This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP does not have measure 0 in EXP, then there exist disjoint pairs of NP languages that are P-inseparable, in fact TIME(2(n k))-inseparable. We also relate these conditions to strong hypotheses concerning randomness and genericity of disjoint pairs.

Self-similar fractals arise as the unique attractors of iterated function systems (IFSs) consisting of finitely many contracting similarities satisfying an open set condition. Each point x in such a fractal F arising from an IFS S is naturally regarded as the “outcome” of an infinite coding sequence T (which need not be unique) over the alphabet $\Sigma_k = \{0, \ldots, k-1\}$, where k is the number of contracting similarities in S. A classical theorem of Moran (1946) and Falconer (1989) states that the Hausdorff and packing dimensions of a self-similar fractal coincide with its similarity dimension, which depends only on the contraction ratios of the similarities. The theory of computing has recently been used to provide a meaningful notion of the dimensions of individual points in Euclidean space. In this paper, we use (and extend) this theory to analyze the dimensions of individual points in fractals that are computably self-similar, meaning that they are unique attractors of IFSs that are computable and satisfy the open set condition. Our main theorem states that, if $F \subseteq \mathbb{R}^n$ is any computably self-similar fractal and S is any IFS testifying to this fact, then the dimension identities $\operatorname{dim}(x) = \operatorname{sdim}(F) \operatorname{dim}^{\pi_S}(T)$ and $\operatorname{Dim}(x) = \operatorname{sdim}(F) \operatorname{Dim}^{\pi_S}(T)$ hold for all $x \in F$ and all coding sequences T for x. In these equations, $\operatorname{sdim}(F)$ denotes the similarity dimension of the fractal F; $\operatorname{dim}(x)$ and $\operatorname{Dim}(x)$ denote the dimension and strong dimension, respectively, of the point x in Euclidean space; and $\operatorname{dim}^{\pi_S}(T)$ and $\operatorname{Dim}^{\pi_S}(T)$ denote the dimension and strong dimension, respectively, of the coding sequence T relative to a probability measure $\pi_S$ that the IFS S induces on the alphabet $\Sigma_k$. The above-mentioned theorem of Moran and Falconer follows easily from our main theorem by relativization. Along the way to our main theorem, we develop the elements of the theory of constructive dimensions relative to general probability measures. The proof of our main theorem uses Kolmogorov complexity characterizations of these dimensions.

The two most important notions of fractal dimension are Hausdorff dimension, developed by Hausdorff [Math. Ann., 79 (1919), pp. 157–179], and packing dimension, developed independently by Tricot [Math. Proc. Cambridge Philos. Soc., 91 (1982), pp. 57–74] and Sullivan [Acta Math., 153 (1984), pp. 259–277]. Both dimensions have the mathematical advantage of being defined from measures, and both have yielded extensive applications in fractal geometry and dynamical systems. Lutz [Proceedings of the 15th IEEE Conference on Computational Complexity, Florence, Italy, 2000, IEEE Computer Society Press, Piscataway, NJ, 2000, pp. 158–169] has recently proven a simple characterization of Hausdorff dimension in terms of gales, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension, including constructive, computable, polynomial-space, polynomial-time, and finite-state dimensions. Work by several investigators has already used these effective dimensions to shed significant new light on a variety of topics in theoretical computer science. In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of—and every bit as simple as—the gale characterization of Hausdorff dimension. Effectivizing our gale characterization of packing dimension produces a variety of effective strong dimensions, which are exact duals of the effective dimensions mentioned above. In general (and in analogy with the classical fractal dimensions), the effective strong dimension of a set or sequence is at least as great as its effective dimension, with equality for sets or sequences that are sufficiently regular. We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression. Aside from the above characterization of packing dimension, our two main theorems are the following. 1. If $\vec{\beta} = (\beta_0,\beta_1,\ldots)$ is a computable sequence of biases that are bounded away from 0 and R is random with respect to $\vec{\beta}$, then the dimension and strong dimension of R are the lower and upper average entropies, respectively, of $\vec{\beta}$. 2. For each pair of $\Delta^0_2$-computable real numbers $0 < \alpha \le \beta \le 1$, there exists $A \in {\rm E}$ such that the polynomial-time many-one degree of A has dimension $\alpha$ in E and strong dimension $\beta$ in E. Our proofs of these theorems use a new large deviation theorem for self-information with respect to a bias sequence $\vec{\beta}$ that need not be convergent.

The "analyst's traveling salesman theorem" of geometric measure theory characterizes those subsets of Euclidean space that are contained in curves of finite length. This result, proven for the plane by Jones (1990) and extended to higher-dimensional Euclidean spaces by Okikiolu (1992), says that a bounded set K is contained in some curve of finite length if and only if a certain "square beta sum", involving the "width of K" in each element of an infinite system of overlapping "tiles" of descending size, is finite. In this paper we characterize those points of Euclidean space that lie on computable curves of finite length. We do this by formulating and proving a computable extension of the analyst's traveling salesman theorem. Our extension, the computable analyst's traveling salesman theorem, says that a point in Euclidean space lies on some computable curve of finite length if and only if it is "permitted" by some computable "Jones constriction". A Jones constriction here is an explicit assignment of a rational cylinder to each of the above-mentioned tiles in such a way that, when the radius of the cylinder corresponding to a tile is used in place of the "width of K" in each tile, the square beta sum is finite. A point is permitted by a Jones constriction if it is contained in the cylinder assigned to each tile containing the point. The main part of our proof is the construction of a computable curve of finite length traversing all the points permitted by a given Jones constriction. Our construction uses the main ideas of Jones's "farthest insertion" construction, but takes a very different form, because, having no direct access to the points permitted by the Jones constriction, our algorithm must work exclusively with the constriction itself

A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martingales. When the resource bound $\Delta$ (a parameter of the theory) is unrestricted, the resulting dimension is precisely the classical Hausdorff dimension (sometimes called "fractal dimension"). Other choices of the parameter $\Delta$ yield internal dimension theories in E, E 2 , ESPACE, and other complexity classes, and in the class of all decidable problems. In general, if $\mathcal{C}$ is such a class, then every set X of languages has a dimension in $\mathcal{C}$, which is a real number $\dim (X \mid \mathcal{C}) \in [0, 1]$. Along with the elements of this theory, two preliminary applications are presented: For every real number $0 \le \alpha \le \frac 1 2$, the set ${\rm FREQ}(\le \alpha)$, consisting of all languages that asymptotically contain at most $\alpha$ of all strings, has dimension $\mathcal{H}(\alpha)$---the binary entropy of $\alpha$---in E and in E 2 . For every real number $0 \le \alpha \le 1$, the set ${\rm SIZE}(\alpha \frac {2^n} n)$, consisting of all languages decidable by Boolean circuits of at most $\alpha \frac {2^n} n$ gates, has dimension $\alpha$ in ESPACE.

A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martin-gales. When the resource bound /spl Delta/(a parameter of the theory) is unrestricted, the resulting dimension is precisely the classical Haludolff dimension (sometimes called "fractal dimension"). Other choices of the parameter /spl Delta/ yield internal dimension theories in E, E/sub 2/, ESPACE, and other complexity classes, and in the class of all decidable problems. In general, if C is such a class, then every set X of languages has a dimension in C, which is a real number dim(X|C)/spl isin/[0, 1]. Along with the elements of this theory two preliminary applications are presented: 1. For every real number 0/spl les//spl alpha//spl les/ 1/2 , the set FREQ(/spl ap//spl alpha/), consisting of all languages that asymptotically contain at most /spl alpha/ of all strings, has dimension /spl Hscr/(/spl alpha/)-the binary entropy of /spl alpha/-in E and in E/sub 2/. 2. For every real number 0/spl les//spl alpha//spl les/1, the set SIZE(/spl alpha/2/sup n//n), consisting of all languages decidable by Boolean circuits of at most /spl alpha/2/sup n//n gates, has dimension /spl alpha/ in ESPACE.

Given a real number $\alpha < 1$, every language that is weakly $\leq_{n^{\alpha / 2} - {\rm T}}^{{\rm P}} $-hard for E or weakly $\leq_{n^{\alpha} - {\rm T}}^{\rm P}$-hard for E 2 is shown to be exponentially dense. This simultaneously strengthens the results of Lutz and Mayordomo (1994) and Fu (1995).

The effect of query order on NP-completeness is investigated. A sequence D/spl I.oarr/=(D/sub 1/,...,D/sub k/) of decision problems is defined to be sequentially complete for NP if each D/sub i//spl isin/NP and every problem in NP can be decided in polynomial time with one query to each of D/sub 1/,...,D/sub k/ in this order. It is shown that, if NP contains a language that is p-generic in the sense of Ambos-Spies, Fleischhack, and Huwig (1987), then for every integer k/spl ges/2, there is a sequence D/spl I.oarr/=(d/sub 1/,...,D/sub k/) such that D is sequentially complete for NP, but no nontrivial permutation (D(i/sub 1/),...,D(i/sub k/)) of D/spl I.oarr/ is sequentially complete for NP. It follows that such a sequence D/spl I.oarr/ exists if there is any strongly positive, p-computable probability measure /spl nu/ such that "/sub p/(NP)/spl ne/0.

The resource-bounded measures of complexity classes are shown to be robust with respect to certain changes in the underlying probability measure. Specifically, for any real number $\delta > 0$, any uniformly polynomial-time computable sequence $\mv{\beta} = (\beta_0, \beta_1, \beta_2, \ldots )$ of real numbers (biases) $\beta_i \in [\delta, 1-\delta]$, and for any complexity class ${\bf \cal C}$ (such as P, NP, BPP, P/Poly, PH, PSPACE, etc.) that is closed under positive, polynomial-time, truth-table reductions with queries of at most linear length, it is shown that the following two conditions are equivalent.(1) ${\bf \cal C}$ has p-measure 0 (respectively, measure 0 in E, measure 0 in E 2 ) relative to the coin-toss probability measure given by the sequence ${\mv{\beta}}$.(2) ${\bf \cal C}$ has p-measure 0 (respectively, measure 0 in E, measure 0 in E 2 ) relative to the uniform probability measure.The proof introduces three techniques that may be useful in other contexts, namely, (i) the transformation of an efficient martingale forone probability measure into an efficient martingale for a "nearby" probability measure; (ii) the construction of a positive bias reduction, a truth-table reduction that encodes a positive, efficient, approximate simulation of one bias sequence by another; and (iii) the use of such a reduction to dilate an efficient martingale for the simulated probability measure into an efficient martingale for the simulating probability measure.

A general theory of resource-bounded measurability and measure is developed. Starting from any feasible probability measure /spl nu/ on the Canter space C (the set of all decision problems) and any suitable complexity class C/spl sube/C, the theory identifies the subsets of C that are /spl nu/-measurable in C and assigns measures to these sets, thereby endowing C with internal measure-theoretic structure. Classes C to which the theory applies include various exponential time and space complexity classes, the class of all decidable languages, and the Canter space C itself, on which the resource-bounded theory is shown to agree with the classical theory. The sets that are /spl nu/-measurable in C are shown to form an algebra relative to which /spl nu/-measure is well-behaved (monotone, additive, etc.). This algebra is also shown to be complete (subsets of measure 0 sets are measurable) and closed under sufficiently uniform infinitary unions and intersections, and /spl nu/-measure in C is shown to have the appropriate additivity and monotone convergence properties with respect to such infinitary operations. A generalization of the classical Kolmogorov zero-one law is proven, showing that when /spl nu/ is any feasible coin-toss (i.e., product) probability measure on C, every set that is /spl nu/-measurable in C and (like most complexity classes) invariant under finite alterations must have /spl nu/-measure 0 or /spl nu/-measure 1 in C. The theory presented here is based on resource-bounded martingale splitting operators, which are type-2 functionals, each of which maps N/spl times/D/sub /spl nu// into D/sub /spl nu///spl times/D/sub /spl nu//, where D/sub /spl nu// is the set of all /spl nu/-martingales. This type-2 aspect of the theory appears to be essential for general /spl nu/-measure in complexity classes C, but the sets of /spl nu/-measure 0 or 1 in C are shown to be characterized by the success conditions for martingales (type-1 functions) that have been used in resource-bounded measure to date.

Given a real number /spl alpha/<1, every language that is weakly /spl les//sub n/spl alpha//2-T//sup P/-hard for E or weakly /spl les//sub n/spl alpha/-T//sup P/-hard for E/sub 2/ is shown to be exponentially dense. This simultaneously strengthens results of J.H. Lutz and E. Mayordomo (1994) and B. Fu (1995).

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

Measure-theoretic aspects of the $\leq _{\text{m}}^{\text{P}}$-reducibility structure of the exponential time complexity classes ${\text{E}} = {\text{DTIME}}(2^{{\text{linear}}} )$ and ${\text{E}}_2 = {\text{DTIME}}(2^{{\text{polynomial}}} )$ are investigated. Particular attention is given to the complexity (measured by the size of complexity cores) and distribution (abundance in the sense of measure) of languages that are $\leq _{\text{m}}^{\text{P}}$-hard for E and other complexity classes. Tight upper and lower bounds on the size of complexity cores of hard languages are derived. The upper bound says that the $\leq _{\text{m}}^{\text{P}}$-hard languages for E are unusually simple, in the sense that they have smaller complexity cores than most languages in E. It follows that the $\leq _{\text{m}}^{\text{P}}$-complete languages for E form a measure 0 subset of E (and similarly in ${\text{E}}_2$). This latter fact is seen to be a special case of a more general theorem, namely, that every$\leq _{\text{m}}^{\text{P}}$-degree (e.g., the degree of all $\leq _{\text{m}}^{\text{P}}$-complete languages for NP) has measure 0 in E and in ${\text{E}}_2$.

A weak completeness phenomenon is investigated in the complexity class ${\text{E}} = {\text{DTIME}}(2^{{\text{linear}}} )$. According to standard terminology, a language H is $ \leq _m^{\text{P}} $-hard for E if the set ${\text{P}}_m (H)$, consisting of all languages $A \leq _m^{\text{P}} H$, contains the entire class E. A language C is $ \leq _m^{\text{P}} $-complete for E if it is $ \leq _m^{\text{P}} $-hard for E and an element of E. Generalizing this, a language H is weakly$ \leq _m^{\text{P}} $-hard for E if the set ${\text{P}}_m (H)$ does not have measure 0 in E. A language C is weakly$ \leq _m^{\text{P}} $-complete for E if it is weakly $ \leq _m^{\text{P}} $-hard for E and an element of E. The main result of this paper is the construction of a language that is weakly $ \leq _m^{\text{P}} $-complete, but not $ \leq _m^{\text{P}} $-complete, for E. The existence of such languages implies that previously known strong lower bounds on the complexity of weakly $ \leq _m^{\text{P}} $-hard problems for E (given by work of Lutz, Mayordomo, and Juedes) are indeed more general than the corresponding bounds for $ \leq _m^{\text{P}} $-hard problems for E. The proof of this result introduces a new diagonalization method called martingale diagonalization. Using this method, one simultaneously develops an infinite family of polynomial time computable martingales (betting strategies) and a corresponding family of languages that defeat these martingales (prevent them from winning too much money) while also pursuing another agenda. Martingale diagonalization may be useful for a variety of applications.

The main theorem of this paper is that, for every real number $\alpha < 1$ (e.g., $\alpha = 0.99$), only a measure 0 subset of the languages decidable in exponential time are $ \leqslant _{n^\alpha - tt}^{\text{p}} $-reducible to languages that are not exponentially dense. Thus every$ \leqslant _{n^\alpha - tt}^{\text{p}} $hard language for E is exponentially dense. This strengthens Watanabe’s 1987 result, that every $ \leqslant _{(\log n) - tt}^{\text{p}} $-hard language for E is exponentially dense. The combinatorial technique used here, the sequentially most frequent query selection, also gives a new, simpler proof of Watanabe’s result. The main theorem also has implications for the structure of NP under strong hypotheses. Ogiwara and Watanabe (1991) have shown that the hypothesis ${\text{P}} \ne {\text{NP}}$ implies that every $ \leqslant _{btt}^{\text{p}} $ -hard language for NP is nonsparse (i.e., not polynomially sparse). Their technique does not appear to allow significant relaxation of either the query bound or the sparseness criterion. It is shown here that a stronger hypothesis—namely, that NP does not have measure 0 in exponential time—implies the stronger conclusion that, for every real $\alpha < 1$, every $ \leqslant _{n^\alpha - tt}^{\text{p}} $-hard language for NP is exponentially dense. Evidence is presented that this stronger hypothesis is reasonable. The proof of the main theorem uses a new, very general weak stochasticity theorem, ensuring that almost every language in E is statistically unpredictable by feasible deterministic algorithms, even with linear nonuniform advice.

Measure-theoretic aspects of the /spl les//sub m//sup P/-reducibility structure of exponential time complexity classes E=DTIME(2/sup linear/) and E/sub 2/=DTIME(2/sup polynomial/) are investigated. Particular attention is given to the complexity (measured by the size of complexity cores) and distribution (abundance in the sense of measure) of languages that are /spl les//sub m//sup P/-hard for E and other complexity classes. Tight upper and lower bounds on the size of complexity cores of hard languages are derived. The upper bounds say that the /spl les//sub m//sup P/-hard languages for E are unusually simple in, the sense that they have smaller complexity cores than most languages in E. It follows that the /spl les//sub m//sup P/-complete languages for E form a measure 0 subset of E (and similarly in E/sub 2/). This latter fact is seen to be a special case of a more general theorem, namely, that every /spl les//sub m//sup P/-degree (e.g. the degree of all /spl les//sub m//sup P/-complete languages for NP) has measure 0 in E and in E/sub 2/.>

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

It is known from work of Bennett and Gill [SIAM J. Comput., 10 (1981), pp. 96–113] and of Ambos-Spies [in Proc. 1st Structure in Complexity Theory Conference, 1986, pp. 23–34] that the following conditions are equivalent: (i) $L \in {\text{BPP}}$. (ii) For almost all oracles A, $L \in {\text{P}}^A $. It is shown here that the following conditions are also equivalent to (i) and (ii): (iii) The set of oracles A for which $L \in {\text{P}}^A $ has pspace-measure 1. (iv) For every pspace-random oracle A, $L \in {\text{P}}^A $. It follows from this characterization (and its proof) that almost every $A \in {\text{ESPACE}}$ is $ \leqslant _T^{\text{P}} $-hard for ${\text{BPP}}^A $. Succinctly, the main content of the proof is that pseudorandom generators exist relative to every pseudorandom oracle.

This paper presents resource-bounded category and resource-bounded measure—two new tools for computational complexity theory—and some applications of these tools to the structure theory of exponential complexity classes. Resource-bounded category, a complexity-theoretic generalization of the Baire category method, defines nontrivial ideals of meager subsets of E, ESPACE, and other complexity classes. Similarly, resource-bounded measure, a generalization of Lebesgue measure theory, defines the measure 0 subsets of complexity classes. Properties developed here include a useful characterization of meager sets in terms of resource-bounded Banach–Mazur games. Resource-bounded category and measure are applied to the investigation of uniform versus nonuniform complexity. Kannan’s theorem that $\text{ESPACE} \nsubseteq \text{P}/\text{Poly}$ is extended by showing that ${{{\text{P}}} / {{\text{Poly}}}} \cap {\text{ESPACE}}$ is only a meager, measure 0 subset of ESPACE. A theorem of Huynh is extended similarly by showing that all but a meager, measure 0 subset of the languages in {\text{ESPACE}} have high space-bounded Kolmogorov complexity. A new hierarchy of exponential classes is introduced and used to refine known relationships between nonuniform complexity and time complexity. Known properties of hard languages are also extended. Recent results of Schoning and Huynh state that any language L that is $\leqq _m ^{\text{P}}$-hard for E or $\leqq _T ^{\text{P}}$-hard for {\text{ESPACE}} cannot be feasibly approximated. It is proven here that this conclusion in fact holds unless only a meager subset of E is $\leqq _m ^{\text{P}}$-reducible to L and only a meager, measure 0 subset of {\text{ESPACE}} is $\leqq_{m}^{\text{PSPACE}}$ reducible to L. This suggests a new lower bound method which may be useful in interesting cases.