CS Paper Radar

Reconfiguration of Time-Bounded Descriptions

Dimitrios Myrisiotis

cs.CC cs.DM ·submitted 2026-11-06 05:49 UTC · v1

Abstract

Time-bounded Kolmogorov complexity measures a string by the length of its shortest program that prints it within a deadline. An adjunction-universal machine (Bauwens, Kozachinskiy, and Shen, arXiv, 2025) is a Turing machine that simulates every Turing machine $M$ on every input $z$ with polynomial overhead when given a code of $M$, computable from $M$ in polynomial time, followed by $z$ unchanged. Any two adjunction-universal machines give the same measure up to an additive constant and a polynomial change of the deadline. However, this measure records only the shortest program for a string. We study all programs of one length that print a string within one deadline, join two of them when they differ in one bit, and ask when this graph is connected. Fix any adjunction-universal machine. For almost all $m$-bit strings and every deadline beyond some polynomial, the graph is disconnected at program length $m+O(1)$ and has at least $2^{m-O(1)}$ components at length $2m+3$. In contrast, we build an adjunction-universal machine in which every such graph is connected or empty, at every deadline, once the program length reaches a computable threshold that is at most exponential in the length of the string. Exponential thresholds are unavoidable: for every adjunction-universal machine with such thresholds and every large $m$, more than three quarters of the $m$-bit strings need a threshold exponential in $m$. For our machine, above the threshold, every program for the string is within three bit flips of a connected set of fastest programs for the string, along a path inside the graph, at every deadline by which that program halts. For this machine, deciding whether two given programs are connected in this graph is $\mathsf{PSPACE}$-complete when the input is the string, the deadline in unary and the two programs; for each fixed string it takes polynomial time.

Comment
50 pages

Closest papers

Nearest neighbours by meaning across the whole index.

The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach

cs.AI cs.CCcs.IT ·2026-08-17 ·Rafael Pass
similarity 0.61
Abstract

In a world where valuable artifacts are increasingly created, completed, or processed by LLMs, the central economic question is not only what the LLM can produce, but what \emph{value} remains in the inputs (i.e., the prompts) we provide to it. Given a prompt, hint, critique, problem statement, or partial solution that helps an LLM produce an artifact $z$---a proof, program, design, or scientific hypothesis---how should we measure the value of that input? Intuitively, an input is valuable when it makes the target artifact easier for the model to generate: either by increasing its sampling probability, or by reducing the thinking time needed to find it. We propose a computational Levin--Kolmogorov complexity approach to this problem, by appropriately replacing the universal Turing machine in the classical definitions by the LLM itself. Concretely, we introduce an LLM-relative notion of \emph{probabilistic Levin--Kolmogorov complexity} $pKt$---treating the model's thinking as the random tape of the program, and charging logarithmically for it in Levin's manner---and define prompt value as algorithmic mutual information with respect to $pKt$. This captures the intuition above: a prompt having $b$ bits of value for an artifact $z$ makes $z$ $2^b$ times ``easier to obtain'', by multiplying the success probability by $2^b$, by dividing the required computation by $2^b$, or by any corresponding tradeoff between probability and computation. In contrast to the classical notion of algorithmic mutual information, ours is efficiently estimable. We additionally show that, under a natural reproduction experiment, a prompt value of \(b\) bits means that reproducing \(z\) without the prompt has median token cost \(2^b\) times that of reproducing it with the prompt.

0.35

Analysing Busy Beaver Machines (Or How to Find Ossified Ocelots)

cs.FL cs.LO ·2026-11-13 ·James Harland
similarity 0.60
Abstract

The busy beaver problem involves working with machines which can produce very large numbers, both for the output of certain Turing machines and for the number of steps taken to execute them. Given that these numbers can involve thousands of digits, it is crucial to have a means of proving properties of the relevant machines which allow manipulation of such large numbers. In this paper we introduce the notion of \textit{shape computations} as a means of isolating key properties that allow efficient execution of the relevant Turing machines based on verifiable properties of state transitions. In particular, this notion allows us to provide an analytical result which demonstrates the quadratic relationship between the size of the output and the number of steps required to generate it. We have also developed an initial implementation of our approach, and we provide empirical evaluation of it on a suite of 240 example machines.

0.22

Breaking the Space Barrier and its Application to Language Model Inference

cs.AI cs.CC ·2026-10-06 ·Arip Asadulaev
theory similarity 0.60
Abstract

Language models are more and more often asked for structured output: JSON that follows a schema, or a tool call with typed arguments. A small machine, an automaton, enforces the format by forbidding the tokens that would break it. We observe that this machine has a rare property: from any of its states, each token leads along exactly one path. Graphs in which only a few paths join any two points are a classical object of complexity theory, and our theoretical result settles an open question about them: one can decide whether such a graph connects two points while verifying that it really has few paths, with very little memory. Precisely, the problem lies in the classes ReachUL, LOGDCFL, C=L and SC2, and needs only O(log2 n/ log log n) space, below the classical O(log2 n) of Savitch's theorem. The constructions behind the proofs become an inference engine: text the format forces is written without running the model, the mask is recomputed on the GPU without any table, recursive formats use a small stack, every output stays valid under a token limit, and independent fields are decoded in parallel and verified. On one 16 GB Apple M2 Pro with Qwen3.5-2B and 4B, against MLX with llguidance, the standard setup for this hardware, schema-constrained extraction finishes 1.2- 1.3x sooner with the same answers, a grammar costs 3 MB instead of up to 1.5 GB, one server holds sixteen grammars where tables run out of memory, and sixteen tool-calling agents finish 2.5x sooner.

0.31

Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification

cs.LG cs.CCcs.LOcs.NE ·2026-11-02 ·Olivier Bournez, Johanne Cohen, Adrian Wurm
top venuetheory similarity 0.60
Abstract · 41 pages, 6 figures, 2 tables. Accepted at NeurIPS 2026

We study the iterates of a fixed ReLU network $N$ of width 4, that is, the discrete-time system $x_{k+1} = N(x_k)$ on $[0,1]^4$. Equivalently, $x_k$ is the output of a weight-tied network made of $k$ copies of $N$, or of a recurrent network with no external input, started at $x_0$. We prove that every deterministic Turing machine $M$ admits such a network $N_M$. The network can be constructed in polynomial time from $M$. Each iteration has depth $\mathrm{poly}(|M|)$. The iterates of $N_M$ simulate $M$ exactly on every encoded tape. The number of iterations is proportional to the running time of $M$. Moreover, the fourth coordinate irreversibly flags every point of the convex cube $[0,1]^4$ whose simulation reads an invalid digit. This flag is the certificate that makes hardness reductions sound on convex input regions, the regime of practical verifiers. Convex regions were previously inaccessible because of a continuity obstruction inherent to ReLU networks. The correspondence has three consequences. First, reachability for iterated width-4 ReLU networks spans the full complexity hierarchy along the single axis of the time bound: it is NP-complete for a unary bound, NEXP-complete for a binary bound and RE-complete (undecidable) with no bound. Second, two extra neurons of width suffice to extend the hardness to every common smooth activation: at width 6, the robust verification problem (a promise problem with $δ/2δ$ gap) is NP-complete for $\tanh$, sigmoid, GELU, Swish, ELU, and any polynomial-time-computable continuous non-polynomial activation with a polynomial-time-computable Lipschitz constant. Third, the whole spectrum transfers to discretized Neural ODEs in dimension 5.

0.47

$\ell_p$-Norm Maximization over Zonotopes Is W[1]-Hard

cs.CC cs.CG ·2026-08-16 ·Yang Cao, Haoran Qi, Hanzhi Wang
theory similarity 0.60
Abstract

We study $\ell_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mathrm{poly}(L)$ time, but fixed-parameter tractability in the ambient dimension $d$ was open [FGHS25]. We prove W[1]-hardness and, under the Exponential Time Hypothesis (ETH), exclude $ρ_p(d)L^{o(d)}$ time, even for $5$-sparse generators, by encoding binary CSP constraints with normalized positive cap generators. We also give a deterministic $(1-\varepsilon)$-approximation with $\varepsilon^{-(d-1)/2}$ dependence and, among algorithms with fixed-degree polynomial dependence on $L$, rule out $(1/\varepsilon)^{o(d)}$ dependence under ETH. Support-function duality transfers the results to positive-output two-layer ReLU networks.

0.42

Quantifying the Advantage of Coarser DPOR

cs.PL ·2026-11-13 ·Minjian Zhang, Rupak Majumdar, Umang Mathur, C. -H. Luke Ong
benchmark similarity 0.59
Abstract · 32 pages, 2 figures

Dynamic partial-order reduction (DPOR) has emerged as a promising approach to addressing interleaving explosion in bounded model checking of concurrent programs. Given an equivalence relation on interleavings, the model checker explores a program's executions while minimizing repeated visits to the same class; optimal model checkers avoid such repetition altogether. A coarser equivalence promises faster exploration by reducing the number of classes. This has motivated alternatives to Mazurkiewicz's trace equivalence such as reads-from and reads-value-from equivalence. This promise, however, does not always materialize in practice: while a coarser equivalence can yield exponentially fewer classes on some families of programs, it may offer little or no reduction for the program at hand. We show how to quantify the advantage of coarser equivalences for individual programs. We focus on the problem of counting the reads-from (RF) equivalence classes induced by a given program, as well as the problem of computing the ratio of RF to Mazurkiewicz class counts under sequential consistency. We show that both problems are $\#\mathrm{P}$-hard and that the reduction ratio remains hard to approximate accurately under standard complexity assumptions. Guided by these limits, we present CoEst, a sampling-based algorithm for estimating both the RF count and its ratio to the Mazurkiewicz count. For a fixed number of threads, each trial runs in polynomial time and yields unbiased count estimates. As the number of independent trials grows, the count and ratio estimates converge almost surely to their true values. Our algorithm can provide statistical evidence for deciding whether Mazurkiewicz or RF model checking is likely to be faster for a given program. In experiments across 34 benchmark configurations, our method selects the faster checker in 99.4% of runs using a one-minute estimation budget.

0.36

Asymmetry and Complexity of Nondeterministic Computations

cs.CC ·2026-10-14 ·Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
theory similarity 0.59
Abstract

Symmetry of Information (SoI) [ZL70] is a fundamental theorem of classical Kolmogorov complexity whose status for time-bounded computation is closely related to central open problems in complexity theory and cryptography. In a recent development, [HMO26] showed that SoI fails for $rKt$ complexity, namely in the setting of randomized computation. By contrast, many basic properties of Kolmogorov complexity are known to remain valid in the presence of nondeterminism [HLO26], suggesting that SoI may provide a fruitful structural principle for exploring the relative power of randomness and nondeterminism in computation. Our results reveal that the validity of SoI for nondeterministic computation, namely for $nKt$ complexity, is a subtle question connected to several frontiers. We show that symmetry of information holds on average for randomized extensions of $nKt$, while its worst case validity would imply breakthrough complexity separations. Although the standard cryptographic argument for asymmetry does not extend to the nondeterministic setting, we provide evidence that information remains asymmetric in nondeterministic computations. Among other results, we show that SoI would imply a collapse of exponential time classes to low levels of the polynomial hierarchy. Then, building on the work of [Hir22b, GK22, KK26, HMO26], we develop a general framework connecting symmetry of information, meta-complexity, and explicit constructions in the nondeterministic setting. More precisely, we prove that suitable formulations of these three notions are quantitatively equivalent. We apply different aspects of this correspondence to make progress on complexity lower bounds and on the failure of SoI for nondeterministic computation. These consequences are unconditional and provide some of the strongest known lower bounds in meta-complexity.

0.22

The Complexity of Unpredictability

cs.CC ·2026-11-04 ·Aryan Agarwala, Dani Dorfman
theory similarity 0.59
Abstract

We initiate the study of middle-bit predictors: functions that take as input a string with one missing bit and try to predict that bit. These are closely related to next-bit predictors, a classical object in pseudorandomness. We study the deterministic complexity of computing an unpredictable distribution (UNPRED). Given a list of middle-bit predictors in circuit form and a parameter $ε>0$, output a multiset of strings such that each predictor succeeds with probability less than $1/2+ε$ on a uniformly sampled string from the multiset. We write $\mathsf{UNPRED}^{\mathsf{TC}^1}$ for the restriction to $\mathsf{TC}^1$ predictors. We show that UNPRED offers a unified route towards resolving several major open problems in catalytic computation, the biggest of which is whether deterministic polynomial time (P and FP) can simulate catalytic logspace (CL and SearchCL). It is believed that $\mathsf{SearchCL}\subseteq\mathsf{FP}$. We prove $$\mathsf{UNPRED}\in\mathsf{FP}\implies\mathsf{SearchCL}\subseteq\mathsf{FP}\implies\mathsf{UNPRED}^{\mathsf{TC}^1}\in\mathsf{FP}.$$ Thus, the questions of whether UNPRED is in FP and whether SearchCL is contained in FP are almost equivalent, up to the restriction to $\mathsf{TC}^1$ circuits. We also show that any deterministic polynomial-time algorithm for $\mathsf{UNPRED}^{\mathsf{TC}^1}$ must exploit properties of $\mathsf{TC}^1$ circuits, either in the algorithm itself or in its analysis. To our knowledge, this would also be the first algorithm to use the structure of $\mathsf{TC}^1$ circuits in this way to solve a natural problem, thus advancing our understanding of Boolean circuits. Together, our results provide strong evidence that middle-bit predictors could be the key to unlocking several major open problems in catalytic computation, pseudorandomness, and Boolean circuit complexity.

0.26