skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Proceedings of the 29th International Conference on DNA Computing and Molecular Programming (DNA 29)
Discrete chemical reaction networks formalize the interactions of molecular species in a well-mixed solution as stochastic events. Given their basic mathematical and physical role, the computational power of chemical reaction networks has been widely studied in the molecular programming and distributed computing communities. While for Turing-universal systems there is a universal measure of optimal information encoding based on Kolmogorov complexity, chemical reaction networks are not Turing universal unless error and unbounded molecular counts are permitted. Nonetheless, here we show that the optimal number of reactions to generate a specific count x ∈ ℕ with probability 1 is asymptotically equal to a "space-aware" version of the Kolmogorov complexity of x, defined as K̃s(x) = min_p {|p|/log|p| + log(space(𝒰(p))) : 𝒰(p) = x}, where p is a program for universal Turing machine 𝒰. This version of Kolmogorov complexity incorporates not just the length of the shortest program for generating x, but also the space usage of that program. Probability 1 computation is captured by the standard notion of stable computation from distributed computing, but we limit our consideration to chemical reaction networks obeying a stronger constraint: they "know when they are done" in the sense that they produce a special species to indicate completion. As part of our results, we develop a module for encoding and unpacking any b bits of information via O(b/log{b}) reactions, which is information-theoretically optimal for incompressible information. Our work provides one answer to the question of how succinctly chemical self-organization can be encoded - in the sense of generating precise molecular counts of species as the desired state.  more » « less
Award ID(s):
2211793 1901025
PAR ID:
10499293
Author(s) / Creator(s):
; ;
Editor(s):
Chen, Ho-Lin; Evans, Constantine G.
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Subject(s) / Keyword(s):
chemical reaction networks Kolmogorov complexity stable computation Theory of computation → Models of computation
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Kumar, Amit; Ron-Zewi, Noga (Ed.)
    {"Abstract":["The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the "threshold", and how the hardness of different meta-complexity problems relate to one another, and to the task of function inversion.\r\nIn this work, we present resolutions to some of these questions with respect to the black-box analog of these problems. In more detail, let MK^t_M P[s] denote the language consisting of strings x with K_{M}^t(x) < s(|x|), where K_M^t(x) denotes the t-bounded Kolmogorov complexity of x with M as the underlying (Universal) Turing machine, and let search-MK^t_M P[s] denote the search version of the same problem.\r\nWe show that if for every Universal Turing machine U there exists a 2^{α n}poly(n)-size U-oracle aided circuit deciding MK^t_U P[n-O(1)], then for every function s, and every not necessarily universal Turing machine M, there exists a 2^{α s(n)}poly(n)-size M-oracle aided circuit solving search-MK^t_M P[s(n)]; this in turn yields circuits of roughly the same size for both the Minimum Circuit Size Problem (MCSP), and the function inversion problem, as they can be thought of as instantiating MK^t_M P with particular choices of (a non-universal) TMs M (the circuit emulator for the case of MCSP, and the function evaluation in the case of function inversion).\r\nAs a corollary of independent interest, we get that the complexity of black-box function inversion is (roughly) the same as the complexity of black-box deciding MK^t_U P[n-O(1)] for any universal TM U; that is, also in the worst-case regime, black-box function inversion is "equivalent" to black-box deciding MK^t_U P."]} 
    more » « less
  2. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Santhanam, Rahul (Ed.)
    {"Abstract":["A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-t program generating a given string x is at most s.\r\nIn this work, we consider the more "robust" version of the time-bounded Kolmogorov complexity problem, referred to as the GapMINKT problem, where given a size bound s and a running time bound t, the goal is to determine whether there exists a poly(t,|x|)-time program of length s+O(log |x|) that generates x. We present the first non-trivial search-to-decision reduction R for the GapMINKT problem; R has a running-time bound of 2^{ε n} for any ε > 0 and additionally only queries its oracle on "thresholds" s of size s+O(log |x|). As such, we get that any algorithm with running-time (resp. circuit size) 2^{α s} poly(|x|,t,s) for solving GapMINKT (given an instance (x,t,s), yields an algorithm for finding a witness with running-time (resp. circuit size) 2^{(α+ε) s} poly(|x|,t,s).\r\nOur second result is a polynomial-time search-to-decision reduction for the time-bounded Kolmogorov complexity problem in the average-case regime. Such a reduction was recently shown by Liu and Pass (FOCS'20), heavily relying on cryptographic techniques. Our reduction is more direct and additionally has the advantage of being length-preserving, and as such also applies in the exponential time/size regime.\r\nA central component in both of these results is the use of Kolmogorov and Levin’s Symmetry of Information Theorem."]} 
    more » « less
  3. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Guruswami, Venkatesan (Ed.)
    The Perebor (Russian for "brute-force search") conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ≠ P conjecture (which they predate) and state that for "meta-complexity" problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search. In this paper, we disprove the non-uniform version of the Perebor conjecture for the Time-Bounded Kolmogorov complexity problem. We demonstrate that for every polynomial t(⋅), there exists of a circuit of size 2^{4n/5+o(n)} that solves the t(⋅)-bounded Kolmogorov complexity problem on every instance. Our algorithm is black-box in the description of the Universal Turing Machine U employed in the definition of Kolmogorov Complexity and leverages the characterization of one-way functions through the hardness of the time-bounded Kolmogorov complexity problem of Liu and Pass (FOCS'20), and the time-space trade-off for one-way functions of Fiat and Naor (STOC'91). We additionally demonstrate that no such black-box algorithm can have circuit size smaller than 2^{n/2-o(n)}. Along the way (and of independent interest), we extend the result of Fiat and Naor and demonstrate that any efficiently computable function can be inverted (with probability 1) by a circuit of size 2^{4n/5+o(n)}; as far as we know, this yields the first formal proof that a non-trivial circuit can invert any efficient function. 
    more » « less
  4. ; ; (, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022))
    Mikołaj Bojańczyk and Emanuela Merelli and David P. Woodruff (Ed.)
    The classical coding theorem in Kolmogorov complexity states that if an n-bit string x is sampled with probability δ by an algorithm with prefix-free domain then K(x) ≤ log(1/δ) + O(1). In a recent work, Lu and Oliveira [31] established an unconditional time-bounded version of this result, by showing that if x can be efficiently sampled with probability δ then rKt(x) = O(log(1/δ)) + O(log n), where rKt denotes the randomized analogue of Levin’s Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a O(log(1/δ)) bound instead of the information-theoretic optimal log(1/δ). Motivated by this discrepancy, we investigate optimal coding theorems in the time-bounded setting. Our main contributions can be summarised as follows. • Efficient coding theorem for rKt with a factor of 2. Addressing a question from [31], we show that if x can be efficiently sampled with probability at least δ then rKt(x) ≤ (2 + o(1)) · log(1/δ) +O(log n). As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given x, the code of the sampler, and δ, it outputs, with probability ≥ 0.99, a probabilistic representation of x that certifies this rKt complexity bound. • Optimality under a cryptographic assumption. Under a hypothesis about the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt(x) ≤ (2 − o(1)) · log(1/δ) + poly(log n). Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. • Optimal coding theorem for pKt and unconditional Antunes-Fortnow. We consider pKt complexity [17], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pKt, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [5] which characterizes the worst-case running times of languages that are in average polynomial-time over all P-samplable distributions. 
    more » « less
  5. ; ; (, Natural computing)
    The algorithmic self-assembly of shapes has been considered in several models of self-assembly. For the problem of shape construction, we consider an extended version of the two-handed tile assembly model, which contains positive (attractive) and negative (repulsive) interactions. As a result, portions of an assembly can become unstable and detach. In this model, we utilize fuel-efficient computation to perform Turing machine simulations for the construction of the shape. In this paper, we show how an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile types (based on the shape’s Kolmogorov complexity). We achieve this at O(1) scale factor in this straightforward model, whereas all previous results with sublinear scale factors utilize powerful self-assembly models containing features such as staging, tile deletion, chemical reaction networks, and tile activation/deactivation. Furthermore, the computation and construction in our result only creates constant-size garbage assemblies as a byproduct of assembling the shape. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email