Arrow Research search

Author name cluster

Jack H. Lutz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

31 papers
2 author rows

Possible papers

31

MFCS Conference 2024 Conference Paper

Algorithmic Dimensions via Learning Functions

  • Jack H. Lutz
  • Andrei N. Migunov

We characterize the algorithmic dimensions (i. e. , the lower and upper asymptotic densities of information) of infinite binary sequences in terms of the inability of learning functions having an algorithmic constraint to detect patterns in them. Our pattern detection criterion is a quantitative extension of the criterion that Zaffora Blando used to characterize the algorithmically random (i. e. , Martin-Löf random) sequences. Our proof uses Lutz’s and Mayordomo’s respective characterizations of algorithmic dimension in terms of gales and Kolmogorov complexity.

Details

MFCS Conference 2023 Conference Paper

A Weyl Criterion for Finite-State Dimension and Applications

  • Jack H. Lutz
  • Satyadev Nandakumar
  • Subin Pulari

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.

Details

I&C Journal 2023 Journal Article

Extending the reach of the point-to-set principle

  • Jack H. Lutz
  • Neil Lutz
  • Elvira Mayordomo

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 R n. 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.

Details DOI

I&C Journal 2021 Journal Article

Computing absolutely normal numbers in nearly linear time

  • Jack H. Lutz
  • Elvira Mayordomo

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 n polylog ( n ) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.

Details DOI

TCS Journal 2020 Journal Article

Robust biomolecular finite automata

  • Titus H. Klinge
  • James I. Lathrop
  • Jack H. Lutz

We present a uniform method for translating an arbitrary nondeterministic finite automaton (NFA) into a deterministic mass action input/output chemical reaction network (I/O CRN) that simulates it. The I/O CRN receives its input as a continuous time signal consisting of concentrations of chemical species that vary to represent the NFA's input string in a natural way. The I/O CRN exploits the inherent parallelism of chemical kinetics to simulate the NFA in real time with a number of chemical species that is linear in the size of the NFA. We prove that the simulation is correct and that it is robust with respect to perturbations of the input signal, the initial concentrations of species, the output (decision), and the rate constants of the reactions of the I/O CRN.

Details DOI

TCS Journal 2018 Journal Article

Mutual dimension and random sequences

  • Adam Case
  • Jack H. Lutz

If S and T are infinite sequences over a finite alphabet, then the lower and upper mutual dimensions m d i m ( S: T ) and M d i m ( S: T ) are the upper and lower densities of the algorithmic information that is shared by S and T. In this paper we investigate the relationships between mutual dimension and coupled randomness, which is the algorithmic randomness of two sequences R 1 and R 2 with respect to probability measures that may be dependent on one another. For a restricted but interesting class of coupled probability measures we prove an explicit formula for the mutual dimensions m d i m ( R 1: R 2 ) and M d i m ( R 1: R 2 ), and we show that the condition M d i m ( R 1: R 2 ) = 0 is necessary but not sufficient for R 1 and R 2 to be independently random. We also identify conditions under which Billingsley generalizations of the mutual dimensions m d i m ( S: T ) and M d i m ( S: T ) can be meaningfully defined; we show that under these conditions these generalized mutual dimensions have the “correct” relationships with the Billingsley generalizations of d i m ( S ), D i m ( S ), d i m ( T ), and D i m ( T ) that were developed and applied by Lutz and Mayordomo; and we prove a divergence formula for the values of these generalized mutual dimensions.

Details DOI

FOCS Conference 2012 Conference Paper

The Tile Assembly Model is Intrinsically Universal

  • David Doty
  • Jack H. Lutz
  • Matthew J. Patitz
  • Robert Schweller
  • Scott M. Summers
  • Damien Woods

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).

Details

TCS Journal 2011 Journal Article

A divergence formula for randomness and dimension

  • Jack H. Lutz

If S is an infinite sequence over a finite alphabet Σ and β is a probability measure on Σ, then the dimension of S with respect to β, written dim β ( S ), is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension dim ( S ) when β is the uniform probability measure. This paper shows that dim β ( S ) and its dual Dim β ( S ), the strong dimension of S with respect to β, can be used in conjunction with randomness to measure the similarity of two probability measures α and β on Σ. Specifically, we prove that the divergence formula dim β ( R ) = Dim β ( R ) = H ( α ) H ( α ) + D ( α ∥ β ) holds whenever α and β are computable, positive probability measures on Σ and R ∈ Σ ∞ is random with respect to α. In this formula, H ( α ) is the Shannon entropy of α, and D ( α ∥ β ) is the Kullback–Leibler divergence between α and β. We also show that the above formula holds for all sequences R that are α -normal (in the sense of Borel) when dim β ( R ) and Dim β ( R ) are replaced by the more effective finite-state dimensions dim FS β ( R ) and Dim FS β ( R ). In the course of proving this, we also prove finite-state compression characterizations of dim FS β ( S ) and Dim FS β ( S ).

Details DOI

I&C Journal 2011 Journal Article

Curves that must be retraced

  • Xiaoyang Gu
  • Jack H. Lutz
  • Elvira Mayordomo

We exhibit a polynomial time computable plane curve Γ that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of Γ and every positive integer m, there is some positive-length subcurve of Γ that f retraces at least m times. In contrast, every computable curve of finite length that does not intersect itself has a constant-speed (hence non-retracing) parametrization that is computable relative to the halting problem.

Details DOI

TCS Journal 2011 Journal Article

Effective dimensions and relative frequencies

  • Xiaoyang Gu
  • Jack H. Lutz

Consider the problem of calculating the fractal dimension of a set X consisting of all infinite sequences S over a finite alphabet Σ that satisfy some given condition P on the asymptotic frequencies with which various symbols from Σ appear in S. Solutions to this problem are known in cases where (i) the fractal dimension is classical Hausdorff or packing dimension (by work of Volkmann and Olsen), or (ii) the fractal dimension is effective (even finite-state) and the condition P completely specifies an empirical distribution π over Σ, i. e. , a limiting frequency of occurrence for every symbol in Σ. In this paper, we show how to calculate the finite-state dimension (equivalently, the finite-state compressibility) of such a set X when the condition P only imposes partial constraints on the limiting frequencies of symbols. Our results automatically extend to less restrictive effective fractal dimensions (e. g. , polynomial-time, computable, and constructive dimensions), and they have the classical results (i) as immediate corollaries. Our methods are nevertheless elementary and, in most cases, simpler than those by which the classical results were obtained.

Details DOI

TCS Journal 2009 Journal Article

Strict self-assembly of discrete Sierpinski triangles

  • James I. Lathrop
  • Jack H. Lutz
  • Scott M. Summers

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses the more challenging problem of the strict self-assembly of discrete Sierpinski triangles, i. e. , the task of tiling a discrete Sierpinski triangle and nothing else. We first prove that the standard discrete Sierpinski triangle cannot strictly self-assemble in the Tile Assembly Model. We then define the fibered Sierpinski triangle, a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of optimal counters, coupled with measured delay and corner-turning operations. We verify our strict self-assembly using the local determinism method of Soloveichik and Winfree (2007).

Details DOI

I&C Journal 2007 Journal Article

Dimensions of Copeland–Erdös sequences

  • Xiaoyang Gu
  • Jack H. Lutz
  • Philippe Moser

The base-k Copeland–Erdös sequence given by an infinite set A of positive integers is the infinite sequence CEk(A) formed by concatenating the base-k representations of the elements of A in numerical order. This paper concerns the following four quantities. • The finite-state dimension dim fs (CEk(A)), a finite-state version of classical Hausdorff dimension introduced in 2001. • The finite-state strong dimension Dim fs (CEk(A)), a finite-state version of classical packing dimension introduced in 2004. This is a dual of dim fs (CEk(A)) satisfying Dim fs (CEk(A)))⩾dim fs (CEk(A)). • The zeta-dimension (Dim ζ (A), a kind of discrete fractal dimension discovered many times over the past few decades. • The lower zeta-dimension dim ζ (A), a dual of Dim ζ (A) satisfying dim ζ (A)⩽Dim ζ (A). We prove the following. d im fs (CEk(A))⩾dim ζ (A). This extends the 1946 proof by Copeland and Erdös that the sequence (CEk(PRIMES)) is Borel normal. D im fs (CEk(A))⩾Dim ζ (A). T hese bounds are tight in the strong sense that these four quantities can have (simultaneously) any four values in [0, 1] satisfying the four above-mentioned inequalities.

Details DOI

I&C Journal 2007 Journal Article

Finite-state dimension and real arithmetic

  • David Doty
  • Jack H. Lutz
  • Satyadev Nandakumar

We use entropy rates and Schur concavity to prove that, for every integer k ⩾2, every nonzero rational number q, and every real number α, the base-k expansions of α, q + α, and qα all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives a new proof of, Wall’s 1949 theorem stating that the sum or product of a nonzero rational number and a Borel normal number is always Borel normal.

Details DOI

MFCS Conference 2006 Conference Paper

Dimension Characterizations of Complexity Classes

  • Xiaoyang Gu
  • Jack H. Lutz

Abstract We use derandomization to show that sequences of positive pspace-dimension – in fact, even positive Δ \(^{\rm p}_{\rm k}\) -dimension for suitable k – have, for many purposes, the full power of random oracles. For example, we show that, if S is any binary sequence whose Δ \(^{\rm p}_{\rm 3}\) -dimension is positive, then BPP ⊆ P S and, moreover, every BPP promise problem is P S -separable. We prove analogous results at higher levels of the polynomial-time hierarchy. The dimension-almost-class of a complexity class \(\mathcal{C}\), denoted by dimalmost- \(\mathcal{C}\), is the class consisting of all problems A such that \(A \in \mathcal{C}^S\) for all but a Hausdorff dimension 0 set of oracles S. Our results yield several characterizations of complexity classes, such as BPP = dimalmost-P and AM = dimalmost-NP, that refine previously known results on almost-classes. They also yield results, such as Promise-BPP = almost-P-Sep = dimalmost-P-Sep, in which even the almost-class appears to be a new characterization.

Details

FOCS Conference 2006 Conference Paper

Points on Computable Curves

  • Xiaoyang Gu
  • Jack H. Lutz
  • Elvira Mayordomo

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

Details

I&C Journal 2005 Journal Article

Weakly useful sequences

  • Stephen A. Fenner
  • Jack H. Lutz
  • Elvira Mayordomo
  • Patrick Reardon

An infinite binary sequence x is defined to be (i) strongly useful if there is a computable time bound within which every decidable sequence is Turing reducible to x; and (ii) weakly useful if there is a computable time bound within which all the sequences in a non-measure 0 subset of the set of decidable sequences are Turing reducible to x. Juedes, Lathrop, and Lutz [Theorectical Computer Science 132 (1994) 37] proved that every weakly useful sequence is strongly deep in the sense of Bennett [The Universal Turing Machine: A Half-Century Survey, 1988, 227] and asked whether there are sequences that are weakly useful but not strongly useful. The present paper answers this question affirmatively. The proof is a direct construction that combines the martingale diagonalization technique of Lutz [SIAM Journal on Computing 24 (1995) 1170] with a new technique, namely, the construction of a sequence that is “computably deep” with respect to an arbitrary, given uniform reducibility. The abundance of such computably deep sequences is also proven and used to show that every weakly useful sequence is computably deep with respect to every uniform reducibility.

Details DOI

MFCS Conference 2005 Conference Paper

Zeta-Dimension

  • David Doty
  • Xiaoyang Gu
  • Jack H. Lutz
  • Elvira Mayordomo
  • Philippe Moser

Abstract The zeta-dimension of a set A of positive integers is Dim ζ ( A ) = inf { s | ζ A ( s ) < ∞ }, where \(\zeta_A(s)=\sum_{n\in A}n^{-s}. \) Zeta-dimension serves as a fractal dimension on ℤ + that extends naturally and usefully to discrete lattices such as ℤ d, where d is a positive integer. This paper reviews the origins of zeta-dimension (which date to the eighteenth and nineteenth centuries) and develops its basic theory, with particular attention to its relationship with algorithmic information theory. New results presented include a gale characterization of zeta-dimension and a theorem on the zeta-dimensions of pointwise sums and products of sets of positive integers.

Details

TCS Journal 2004 Journal Article

Finite-state dimension

  • Jack J. Dai
  • James I. Lathrop
  • Jack H. Lutz
  • Elvira Mayordomo

Classical Hausdorff dimension (sometimes called fractal dimension) was recently effectivized using gales (betting strategies that generalize martingales), thereby endowing various complexity classes with dimension structure and also defining the constructive dimensions of individual binary (infinite) sequences. In this paper we use gales computed by multi-account finite-state gamblers to develop the finite-state dimensions of sets of binary sequences and individual binary sequences. The theorem of Eggleston (Quart. J. Math. Oxford Ser. 20 (1949) 31–36) relating Hausdorff dimension to entropy is shown to hold for finite-state dimension, both in the space of all sequences and in the space of all rational sequences (binary expansions of rational numbers). Every rational sequence has finite-state dimension 0, but every rational number in [0, 1] is the finite-state dimension of a sequence in the low-level complexity class AC0. Our main theorem shows that the finite-state dimension of a sequence is precisely the infimum of all compression ratios achievable on the sequence by information-lossless finite-state compressors.

Details DOI

CSL Conference 2003 Conference Paper

The Arithmetical Complexity of Dimension and Randomness

  • John M. Hitchcock
  • Jack H. Lutz
  • Sebastiaan Terwijn

Abstract Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension \(\dim(A) \in [0, 1]\) and a strong dimension Dim( A ) ∈ [0, 1]. Let DIM α and \({\rm DIM}_{str}^\alpha\) be the classes of all sequences of dimension α and of strong dimension α, respectively. We show that DIM 0 is properly \(\Pi^{\rm 0}_{\rm 2}\), and that for all \(\Delta^{\rm 0}_{\rm 2}\) -computable α ∈ (0, 1], DIM α is properly \(\Pi^{\rm 0}_{\rm 3}\). To classify the strong dimension classes, we use a more powerful effective Borel hierarchy where a co-enumerable predicate is used rather than a enumerable predicate in the definition of the \(\Sigma^{\rm 0}_{\rm 1}\) level. For all \(\Delta^{\rm 0}_{\rm 2}\) -computable α ∈ [0, 1), we show that \({\rm DIM}_{str}^\alpha\) is properly in the \(\Pi^{\rm 0}_{\rm 3}\) level of this hierarchy. We show that \({\rm DIM}_{str}^1\) is properly in the \(\Pi^{\rm 0}_{\rm 2}\) level of this hierarchy. We also prove that the class of Schnorr random sequences and the class of computably random sequences are properly \(\Pi^{\rm 0}_{\rm 3}\).

Details

I&C Journal 2003 Journal Article

The dimensions of individual strings and sequences

  • Jack H. Lutz

A constructive version of Hausdorff dimension is developed using constructive supergales, which are betting strategies that generalize the constructive supermartingales used in the theory of individual random sequences. This constructive dimension is used to assign every individual (infinite, binary) sequence S a dimension, which is a real number dim(S) in the interval [0, 1]. Sequences that are random (in the sense of Martin-Löf) have dimension 1, while sequences that are decidable, Σ0 1, or Π0 1 have dimension 0. It is shown that for every Δ0 2-computable real number α in [0, 1] there is a Δ0 2 sequence S such that dim(S)=α. A discrete version of constructive dimension is also developed using termgales, which are supergale-like functions that bet on the terminations of (finite, binary) strings as well as on their successive bits. This discrete dimension is used to assign each individual string w a dimension, which is a nonnegative real number dim(w). The dimension of a sequence is shown to be the limit inferior of the dimensions of its prefixes. The Kolmogorov complexity of a string is proven to be the product of its length and its dimension. This gives a new characterization of algorithmic information and a new proof of Mayordomo’s recent theorem stating that the dimension of a sequence is the limit inferior of the average Kolmogorov complexity of its first n bits. Every sequence that is random relative to any computable sequence of coin-toss biases that converge to a real number β in (0, 1) is shown to have dimension H(β), the binary entropy of β.

Details DOI

I&C Journal 1999 Journal Article

Recursive Computational Depth

  • James I. Lathrop
  • Jack H. Lutz

In the 1980s, Bennett introduced computational depth as a formal measure of the amount of computational history that is evident in an object's structure. In particular, Bennett identified the classes of weakly deep and strongly deep sequences and showed that the halting problem is strongly deep. Juedes, Lathrop, and Lutz subsequently extended this result by defining the class of weakly useful sequences and proving that every weakly useful sequence is strongly deep. The present paper investigates refinements of Bennett's notions of weak and strong depth, called recursively weak depth (introduced by Fenner, Lutz, and Mayordomo) and recursively strong depth (introduced here). It is argued that these refinements naturally capture Bennett's idea that deep objects are those which “contain internal evidence of a nontrivial causal history. ” The fundamental properties of recursive computational depth are developed, and it is shown that the recursively weakly (respectively, strongly) deep sequences form a proper subclass of the class of weakly (respectively, strongly) deep sequences. The above-mentioned theorem of Juedes, Lathrop, and Lutz is then strengthened by proving that every weakly useful sequence is recursively strongly deep. It follows from these results that not every strongly deep sequence is weakly useful, thereby answering a question posed by Juedes.

Details DOI

TCS Journal 1998 Journal Article

Genericity and randomness over feasible probability measures

  • Amy K. Lorentz
  • Jack H. Lutz

This paper investigates the notion of resource-bounded genericity developed by Ambos-Spies, Fleischhack, and Huwig. Ambos-Spies, Neis, and Terwijn have recently shown that every language that is t(n)-random over the uniform probability measure is t(n)-generic. It is shown here that, in fact, every language that is t(n)-random over any strongly positive, t(n)-computable probability measure is t(n)-generic. Roughly speaking, this implies that, when genericity is used to prove a resource-bounded measure result, the result is not specific to the underlying probability measure.

Details DOI

I&C Journal 1996 Journal Article

Completeness and Weak Completeness under Polynomial-Size Circuits

  • David W. Juedes
  • Jack H. Lutz

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

Details DOI

TCS Journal 1996 Journal Article

Cook versus Karp-Levin: Separating completeness notions if NP is not small

  • Jack H. Lutz
  • Elvira Mayordomo

Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than a negligible subset of exponential time), it is shown that there is a language that is ⩽ T P -complete (“Cook complete”), but not ⩽ m P -complete (“Karp-Levin complete”), for NP. This conclusion, widely believed to be true, is not known to follow from P ≠ NP or other traditional complexity-theoretic hypotheses. Evidence is presented that “NP does not have p-measure 0” is a reasonable hypothesis with many credible consequences. Additional such consequences proven here include the separation of many truth-table reducibilities in NP (e. g. , k queries versus k + 1 queries), the class separation E ≠ NE, and the existence of NP search problems that are not reducible to the corresponding decision problems.

Details DOI

TCS Journal 1995 Journal Article

Weak completeness in E and E2

  • David W. Juedes
  • Jack H. Lutz

The notions of weak ⩽m P-completeness for the complexity classes E = DTIME(2linear) and E2 = DTIME(2polynomial) are compared. An element C of one of these classes is weakly ⩽m P- complete for the class if the set Pm(C), consisting of all languages A ⩽m P C, does not have measure 0 in the class. The following two results are proven. 1. (i)|Every problem that is weakly ⩽m P-complete for E is weakly ⩽m P-complete for E2. 2. (ii)|There is a problem in E that is weakly ⩽m P-complete for E2, but not for E.

Details DOI

TCS Journal 1994 Journal Article

Computational depth and reducibility

  • David W. Juedes
  • James I. Lathrop
  • Jack H. Lutz

This paper reviews and investigates Bennett's notions of strong and weak computational depth (also called logical depth) for infinite binary sequences. Roughly, an infinite binary sequence x is defined to be weakly useful if every element of nonnegligible set of decidable sequences is reducible to x in recursively bounded time. It is shown that every weakly useful sequence is strongly deep. This result (which generalizes Bennett's observation that the halting problem is strongly deep) implies that every high Turing degree contains strongly deep sequences. It is also shown that, in the sense of Baire category, almost every infinite binary sequence is weakly deep, but not strongly deep.

Details DOI

TCS Journal 1993 Journal Article

Circuit size relative to pseudorandom oracles

  • Jack H. Lutz
  • William J. Schmidt

Circuit-size complexity is compared with deterministic and nondeterministic time complexity in the presence of pseudorandom oracles. The following separations are shown to hold relative to every pspace-random oracle A, and relative to almost every oracle A∈ESPACE. (i) NP A is not contained in SIZE A (2 αn ) for any real α < 1 3. (ii) E A is not contained in SIZEA( 2n n ). Thus, neither NP A nor E A is contained in P A /Poly. In fact, these separations are shown to hold for almost every n. Since a randomly selected oracle is pspace-random with probability one, (i) and (ii) immediately imply the corresponding random oracle separations, thus improving a result of Bennett and Gill (1981) and answering open questions of Wilson (1985).

Details DOI

FOCS Conference 1993 Conference Paper

The Complexity and Distribution of Hard Problems (Extended Abstract)

  • David W. Juedes
  • Jack H. Lutz

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/. >

Details

TCS Journal 1992 Journal Article

On independent random oracles

  • Jack H. Lutz

It is shown that P(A)∩P(B)=BPPP holds for every algorithmically random oracle A⊕B. This results extends the corresponding “probability one” characterization of Ambos-Spies (1986) and Kurtz (1987).

Details DOI

TCS Journal 1991 Journal Article

An upward measure separation theorem

  • Jack H. Lutz

It is shown that almost every language in ESPACE is very hard to approximate with circuits. It follows that P ≠ BPP implies that E is a measure 0 subset of ESPACE.

Details DOI
v2026.09.13