Search Results

Documents authored by Lutz, Jack H.

Document
DOI: 10.4230/LIPIcs.MFCS.2024.72
Algorithmic Dimensions via Learning Functions

Authors: Jack H. Lutz and Andrei N. Migunov

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
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.
Cite as

Jack H. Lutz and Andrei N. Migunov. Algorithmic Dimensions via Learning Functions. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.MFCS.2024.72,
  author =	{Lutz, Jack H. and Migunov, Andrei N.},
  title =	{{Algorithmic Dimensions via Learning Functions}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{72:1--72:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.72},
  URN =		{urn:nbn:de:0030-drops-206282},
  doi =		{10.4230/LIPIcs.MFCS.2024.72},
  annote =	{Keywords: algorithmic dimensions, learning functions, randomness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.65
A Weyl Criterion for Finite-State Dimension and Applications

Authors: Jack H. Lutz, Satyadev Nandakumar, and Subin Pulari

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
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.
Cite as

Jack H. Lutz, Satyadev Nandakumar, and Subin Pulari. A Weyl Criterion for Finite-State Dimension and Applications. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.MFCS.2023.65,
  author =	{Lutz, Jack H. and Nandakumar, Satyadev and Pulari, Subin},
  title =	{{A Weyl Criterion for Finite-State Dimension and Applications}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.65},
  URN =		{urn:nbn:de:0030-drops-185997},
  doi =		{10.4230/LIPIcs.MFCS.2023.65},
  annote =	{Keywords: Finite-state dimension, Finite-state compression, Weyl’s criterion, Exponential sums, Normal numbers}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.48
Extending the Reach of the Point-To-Set Principle

Authors: Jack H. Lutz, Neil Lutz, and Elvira Mayordomo

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
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.
Cite as

Jack H. Lutz, Neil Lutz, and Elvira Mayordomo. Extending the Reach of the Point-To-Set Principle. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.STACS.2022.48,
  author =	{Lutz, Jack H. and Lutz, Neil and Mayordomo, Elvira},
  title =	{{Extending the Reach of the Point-To-Set Principle}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{48:1--48:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.48},
  URN =		{urn:nbn:de:0030-drops-158585},
  doi =		{10.4230/LIPIcs.STACS.2022.48},
  annote =	{Keywords: algorithmic dimensions, geometric measure theory, hyperspace, point-to-set principle}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.5
Population-Induced Phase Transitions and the Verification of Chemical Reaction Networks

Authors: James I. Lathrop, Jack H. Lutz, Robyn R. Lutz, Hugh D. Potter, and Matthew R. Riley

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)

Abstract
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.
Cite as

James I. Lathrop, Jack H. Lutz, Robyn R. Lutz, Hugh D. Potter, and Matthew R. Riley. Population-Induced Phase Transitions and the Verification of Chemical Reaction Networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lathrop_et_al:LIPIcs.DNA.2020.5,
  author =	{Lathrop, James I. and Lutz, Jack H. and Lutz, Robyn R. and Potter, Hugh D. and Riley, Matthew R.},
  title =	{{Population-Induced Phase Transitions and the Verification of Chemical Reaction Networks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.5},
  URN =		{urn:nbn:de:0030-drops-129583},
  doi =		{10.4230/LIPIcs.DNA.2020.5},
  annote =	{Keywords: chemical reaction networks, molecular programming, phase transitions, population protocols, verification}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.51
Asymptotic Divergences and Strong Dichotomy

Authors: Xiang Huang, Jack H. Lutz, Elvira Mayordomo, and Donald M. Stull

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
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.
Cite as

Xiang Huang, Jack H. Lutz, Elvira Mayordomo, and Donald M. Stull. Asymptotic Divergences and Strong Dichotomy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.STACS.2020.51,
  author =	{Huang, Xiang and Lutz, Jack H. and Mayordomo, Elvira and Stull, Donald M.},
  title =	{{Asymptotic Divergences and Strong Dichotomy}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.51},
  URN =		{urn:nbn:de:0030-drops-119125},
  doi =		{10.4230/LIPIcs.STACS.2020.51},
  annote =	{Keywords: finite-state dimension, finite-state gambler, Kullback-Leibler divergence, normal sequences}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.53
Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension

Authors: Jack H. Lutz and Neil Lutz

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We formulate the conditional Kolmogorov complexity of x given y at precision r, where x and y are points in Euclidean spaces and r is a natural number. We demonstrate the utility of this notion in two ways. 1. We prove a point-to-set principle that enables one to use the (relativized, constructive) dimension of a single point in a set E in a Euclidean space to establish a lower bound on the (classical) Hausdorff dimension of E. We then use this principle, together with conditional Kolmogorov complexity in Euclidean spaces, to give a new proof of the known, two-dimensional case of the Kakeya conjecture. This theorem of geometric measure theory, proved by Davies in 1971, says that every plane set containing a unit line segment in every direction has Hausdorff dimension 2. 2. We use conditional Kolmogorov complexity in Euclidean spaces to develop the lower and upper conditional dimensions dim(x|y) and Dim(x|y) of x given y, where x and y are points in Euclidean spaces. Intuitively these are the lower and upper asymptotic algorithmic information densities of x conditioned on the information in y. We prove that these conditional dimensions are robust and that they have the correct information-theoretic relationships with the well-studied dimensions dim(x) and Dim(x) and the mutual dimensions mdim(x:y) and Mdim(x:y).
Cite as

Jack H. Lutz and Neil Lutz. Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lutz_et_al:LIPIcs.STACS.2017.53,
  author =	{Lutz, Jack H. and Lutz, Neil},
  title =	{{Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.53},
  URN =		{urn:nbn:de:0030-drops-69806},
  doi =		{10.4230/LIPIcs.STACS.2017.53},
  annote =	{Keywords: algorithmic randomness, conditional dimension, geometric measure theory, Kakeya sets, Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.116
Mutual Dimension

Authors: Adam Case and Jack H. Lutz

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We define the lower and upper mutual dimensions mdim(x:y) and Mdim(x:y) between any two points x and y in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by x and y. We show that these quantities satisfy the main desiderata for a satisfactory measure of mutual algorithmic information. Our main theorem, the data processing inequality for mutual dimension, says that, if f : R^m -> R^n is computable and Lipschitz, then the inequalities mdim(f(x):y) <= mdim(x:y) and Mdim(f(x):y) <= Mdim(x:y) hold for all x \in R^m and y \in R^t. We use this inequality and related inequalities that we prove in like fashion to establish conditions under which various classes of computable functions on Euclidean space preserve or otherwise transform mutual dimensions between points.
Cite as

Adam Case and Jack H. Lutz. Mutual Dimension. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 116-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{case_et_al:LIPIcs.STACS.2013.116,
  author =	{Case, Adam and Lutz, Jack H.},
  title =	{{Mutual Dimension}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{116--126},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.116},
  URN =		{urn:nbn:de:0030-drops-39270},
  doi =		{10.4230/LIPIcs.STACS.2013.116},
  annote =	{Keywords: computable analysis, data processing inequality, effective fractal dimensions, Kolmogorov complexity, mutual information}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2461
Intrinsic Universality in Self-Assembly

Authors: David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
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.
Cite as

David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods. Intrinsic Universality in Self-Assembly. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.STACS.2010.2461,
  author =	{Doty, David and Lutz, Jack H. and Patitz, Matthew J. and Summers, Scott M. and Woods, Damien},
  title =	{{Intrinsic Universality in Self-Assembly}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{275--286},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2461},
  URN =		{urn:nbn:de:0030-drops-24619},
  doi =		{10.4230/LIPIcs.STACS.2010.2461},
  annote =	{Keywords: Biological computing, Molecular computation, intrinsic universality, self-assembly}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2471
Inseparability and Strong Hypotheses for Disjoint NP Pairs

Authors: Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
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.
Cite as

Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo. Inseparability and Strong Hypotheses for Disjoint NP Pairs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 395-404, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fortnow_et_al:LIPIcs.STACS.2010.2471,
  author =	{Fortnow, Lance and Lutz, Jack H. and Mayordomo, Elvira},
  title =	{{Inseparability and Strong Hypotheses for Disjoint NP Pairs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{395--404},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2471},
  URN =		{urn:nbn:de:0030-drops-24711},
  doi =		{10.4230/LIPIcs.STACS.2010.2471},
  annote =	{Keywords: Computational Complexity, Disjoint NP-pairs, Resource-Bounded Measure, Genericity}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2267
Curves That Must Be Retraced

Authors: Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
We exhibit a polynomial time computable plane curve ${\bf \Gamma}$ 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 ${\bf\Gamma}$ and every positive integer $m$, there is some positive-length subcurve of ${\bf\Gamma}$ 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.
Cite as

Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo. Curves That Must Be Retraced. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 149-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:OASIcs.CCA.2009.2267,
  author =	{Gu, Xiaoyang and Lutz, Jack H. and Mayordomo, Elvira},
  title =	{{Curves That Must Be Retraced}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{149--160},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2267},
  URN =		{urn:nbn:de:0030-drops-22674},
  doi =		{10.4230/OASIcs.CCA.2009.2267},
  annote =	{Keywords: Computable analysis, computable curve, computational complexity, Hausdorff measure, rectifiable curve}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact