betaFeedback

WorksComputer Science

Reconfiguration of Time-Bounded Descriptions

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 MM on every input zz with polynomial overhead when given a code of MM, computable from MM in polynomial time, followed by zz 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 mm-bit strings and every deadline beyond some polynomial, the graph is disconnected at program length m+O(1)m+O(1) and has at least 2m−O(1)2^{m-O(1)} components at length 2m+32m+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 mm, more than three quarters of the mm-bit strings need a threshold exponential in mm. 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 PSPACE\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.

Introduction

Time-bounded Kolmogorov complexity measures a string by the length of its shortest program on which a fixed universal machine outputs the string within a given number of steps. Suppose that each of two efficient onto machines can run any machine MM by reading a code of MM followed by an unchanged program zz of MM, with polynomial overhead; we call this simulation by adjunction. Then their measures agree up to an additive constant in length and a polynomial change of the deadline (Fact 3.10). That comparison concerns only the shortest description. It says nothing about how the other descriptions of the same string are arranged, or whether one of them can be turned into another by small changes.

This paper studies that arrangement. Fix a machine, a target string, a program length and a deadline. The fiber of the target is the set of all programs of that length that halt with the target as output within the deadline, where two programs are joined when they differ in one bit. We ask whether the fiber is connected, how many components it has, and how hard it is to decide whether two given programs lie in the same component. In this decision problem the input is the target, the deadline in unary and two programs, and a pair that does not lie in the fiber is a no-instance.

Two features of the question shape the answers. First, the fiber contains every program of the given length, not only the programs that begin with one particular code. A path may pass through programs that begin differently, so an argument about the programs beginning with one code, which we call its cylinder, does not decide connectivity of the fiber. Second, connectivity of the fiber is not monotone in the deadline. A larger deadline keeps every old program and every old path, but newly admitted programs can form new components, so a connected fiber can become disconnected at a larger deadline (for the first machine of Theorem 1.2, by Theorems 4.4 and 4.9). A larger program length gives a different cube altogether, rather than a larger subgraph of the old one, so the fragmentation results choose program lengths as functions of the target length.

Graphs of equal-output genotypes under local mutation are studied in the theory of neutral networks. Reidys, Stadler and Schuster study equal-image classes in genotype–phenotype maps [17], and Hu, Banzhaf and Ochoa study finite systems whose genotypes are programs [11]. The questions here differ in their setting: they concern adjunction-universal machines, deadlines counted in the machine’s own transitions, and every description of the given length. Dependence on the choice of machine is also known for other structural properties of descriptions: for the number of descriptions of a string [22], for reductions to the set of random strings [2], and in the distinction between optimality and universality by adjunction [5].

The results concern three conditions on an efficient machine VV, stated precisely in § 2.2. Besides its program, VV may read an auxiliary input; the fibers above use the empty auxiliary input. The machine is onto: every string is the output of some program on the empty auxiliary input.

Next, the machine has the simulation property, the precise form of simulation by adjunction: every machine MM has a code ⟨M⟩V\langle M\rangle_V for VV, computable from MM in polynomial time. For every string zz, the program ⟨M⟩Vz\langle M\rangle_V z outputs M(z)M(z), and it diverges when MM diverges on zz. The simulation takes time polynomial in the running time of MM and the lengths of zz and ⟨M⟩V\langle M\rangle_V, with one polynomial for all MM. Finally, the machine has the interpretation property: given an auxiliary input aa second code ⟨M⟩V′\langle M\rangle'_V of MM, also computable from MM in polynomial time, it runs MM on the program with the same kind of overhead.

We call a machine with the first two properties an adjunction-universal machine, and the three properties together the reference conditions. The name follows the term universal by adjunction, which Bauwens, Kozachinskiy and Shen record, quoting Downey and Hirschfeldt, for machines universal in their sense [5 Sections 2 and 4]. In their definition the string placed before the unchanged programs of a machine need only exist, and no time bound is imposed; here the code is computable from MM in polynomial time and the simulation has polynomial overhead. The rigid reference UU of Definition 3.5, built on a parity-protected encoding of machines, satisfies all three. The programs ⟨M⟩Vz\langle M\rangle_V z that an adjunction-universal machine must run are its mandatory descriptions. Deadlines always count transitions of VV itself, which we call native transitions, and a subscript VV, as in OV(1)O_V(1), marks a constant that may depend on VV.

In short, adjunction forces the fibers of most targets to fragment permanently at suitable lengths. Yet it allows a machine whose fibers are all empty or connected, at every deadline, once the program length reaches a threshold depending on the target, and for most targets the length needed is necessarily exponential in the target length. The same machine shows that deciding connectivity can be hard when the target is part of the input and easy for every fixed target.

Our Results

Table 1 summarizes the results, the program lengths at which they hold, and the distinction between the shape of a fiber and the complexity of querying it. In the table, “one polynomial deadline” means a deadline polynomial in the target length that depends only on the machine, and the exceptional targets are the same at every later deadline. The informal statements after the table present the main results in words, each with a pointer to its precise counterpart in the body.

SettingGuarantee and regimePrecise statements
Every adjunction-universal machineAt N=m+OV(1)N=m+O_V(1), a fraction 1−OV(1/m)1-O_V(1/m) of mm-bit targets has nonempty disconnected fibers at every deadline after one polynomial deadline.Theorem 4.1
Every adjunction-universal machineAt N=2m+3N=2m+3, a fraction 1−OV(log⁡(m+1)/m)1-O_V(\log(m+1)/m) of mm-bit targets has at least 2m−OV(1)2^{m-O_V(1)} components, for every sufficiently large mm and every deadline beyond one polynomial deadline.Theorem 4.9
Every adjunction-universal machineFor m=2km=2^k with k≥2k\ge2, some length N<2m+OV(1)N<2m+O_V(1) has at least 2m/2−12^{m/2-1} components for all but an OV(m−1/2)O_V(m^{-1/2}) fraction of its targets, at every deadline beyond one polynomial deadline.Theorem 4.10 and Corollary 4.11
Two constructed machines satisfying the reference conditionsAt one common early linear deadline and length 2m+32m+3, every sufficiently long target has a connected exponential-size fiber for one machine and an edgeless one for the other.Theorem 4.4
One constructed machine satisfying the reference conditionsEvery fixed target has a computable threshold Nx≤2∣x∣+2+1N_x\le2^{|x|+2}+1; all fibers at or above it are empty or connected at every deadline, with diameter at most 2N+42N+4.Theorem 5.2
Any adjunction-universal machine with such thresholdsFor every sufficiently large mm, more than three quarters of the mm-bit targets require Nx≥2γm−2N_x\ge2^{\gamma m-2}.Theorem 5.5 and Corollary 5.6

Table 1. Selected guarantees for full program fibers. Constants in statements about every adjunction-universal machine may depend on the machine.

SettingGuarantee and regimePrecise statements
Uniform versus fixed-target complexityThe eventual-connectivity machine has a PSPACE-complete full connectivity language, with every fixed-target restriction in P. It is fixed-parameter tractable in target length; the rigid reference UU has a PSPACE-complete fixed-target connectivity problem.Theorem 5.4 and Corollary 5.7
Globally connected targetsEvery finite set is exactly the set of globally connected targets of some machine satisfying the reference conditions. For every adjunction-universal machine, that set is co-c.e., has computably bounded c.e. subsets, and has intrinsic density zero.Theorems 6.3 and 6.6, Corollaries 6.5 and 6.8, and Proposition 6.9

Table 2.

Mandatory descriptions and persistent fragmentation. An adjunction-universal machine must run every program of every source machine, so a suitable source forces descriptions that the machine cannot avoid. We choose sources that give each target several mandatory descriptions far apart in Hamming distance, and we count how many other programs, anywhere in the cube, would be needed to connect them. Here and below, “almost all” refers to the fraction of the mm-bit targets as mm tends to infinity.

Theorem 1.1 (Informal; Theorems 4.1 and 4.9 and Corollary 4.11). Let VV be an adjunction-universal machine. Each of the following holds at every deadline beyond a deadline polynomial in mm, where the polynomial depends only on VV, with the same exceptional targets at all those deadlines.

(1) At program length m+OV(1)m+O_V(1), every mm-bit target has a nonempty fiber, since it has mandatory descriptions there, and all but an OV(1/m)O_V(1/m) fraction of these fibers are disconnected.

(2) At program length exactly 2m+32m+3, for every sufficiently large mm, all but an OV(log⁡(m+1)/m)O_V(\log(m+1)/m) fraction of the mm-bit targets have fibers with at least 2m−OV(1)2^{m-O_V(1)} components.

(3) When m≥4m \ge4 is a power of two, there is a program length below 2m+OV(1)2m+O_V(1), depending only on VV and mm, that gives at least 2m/2−12^{m/2-1} components for all but an OV(m−1/2)O_V(m^{-1/2}) fraction of the mm-bit targets.

The constants hidden in OV(1)O_V(1) come from the length of the code of a fixed source machine, chosen separately for each part. The bounds therefore hold for every adjunction-universal machine, whatever its other programs do.

These bounds start only once the mandatory descriptions have halted. At an earlier deadline a fiber can look entirely different, and there the answer depends on the machine.

Theorem 1.2 (Informal; Theorems 4.4 and 4.9). There are two machines satisfying the three reference conditions that disagree about connectivity at program length 2m+32m+3 and one common deadline linear in mm. For every sufficiently large mm, every mm-bit target has a connected fiber with 2m+12^{m+1} vertices for the first machine and an edgeless fiber with 2m2^m vertices for the second. By contrast, for every adjunction-universal machine, almost all mm-bit targets have disconnected fibers at length 2m+32m+3 at every deadline beyond one polynomial deadline.

The two statements are compatible. A path present at the early deadline is still present later, but programs admitted afterwards form further components. The later statement concerns connectivity of the whole fiber, not the loss of a path that existed earlier.

Eventual connectivity. The fragmentation bounds hold at lengths chosen from the target length. The fibers of a target may be disconnected at those lengths and still be empty or connected at every length beyond a threshold that depends on the target. Our main construction provides this for all targets and all deadlines at once, and it remains hard to query.

Theorem 1.3 (Informal; Theorems 5.2 and 5.4 and Corollaries 5.3 and 5.6). There is a machine satisfying the three reference conditions with the following properties.

  1. For every target xx one can compute a threshold Nx≤2∣x∣+2+1N_x \le2^{|x|+2}+1 such that, at every program length N≥NxN \ge N_x and every deadline, the fiber of xx is empty or connected, with diameter at most 2N+42N+4.

  1. Deciding whether two programs lie in the same fiber component is PSPACE-complete, yet for each fixed target it is decidable in polynomial time.

Conversely, for every adjunction-universal machine with such thresholds and every sufficiently large mm, more than three quarters of the mm-bit targets xx have Nx≥2cVm−2N_x \ge2^{c_Vm-2}, for a constant cV>0c_V>0.

The lower bound concerns program length, not decision time: it says how long programs must be before every fiber of the target is guaranteed to be empty or connected. It comes from the fragmentation argument run at an exponentially large program length, where a disconnected fiber persists at every later deadline.

Fixed and varying targets. The previous theorem separates the complexity of the whole problem from that of each fixed target. Measuring how the running time may depend on the target length gives a finer comparison, even between machines whose connectivity problems are complete for the same class.

Theorem 1.4 (Informal; Corollaries 3.24, 5.7 and 5.8). There are two machines satisfying the three reference conditions whose connectivity problems are both PSPACE-complete. For the first, the machine of Theorem 1.3, one algorithm runs in time 22O(k)ℓO(1)2^{2^{O(k)}}\ell^{O(1)} on queries of length ℓ\ell with targets of length kk. If P differs from PSPACE, no algorithm for this machine runs in time 22O(k)ℓO(1)2^{2^{O(k)}}\ell^{O(1)}. For the second, the problem is already PSPACE-complete at the fixed target 0000, so if P differs from PSPACE it is not fixed-parameter tractable in the target length.

The single-exponential exclusion holds because the hardness reduction uses targets of logarithmic length (Corollary 5.8). No matching double-exponential lower bound on the running time is claimed.

Targets connected at every length and deadline. Write G(V)G(V) for the set of globally connected targets, those whose fibers are empty or connected at every program length and every deadline. This is much stronger than eventual connectivity: one disconnected fiber, at any length and any deadline, excludes a target from G(V)G(V).

Theorem 1.5 (Informal; Theorems 6.2 to 6.4 and 6.6, Corollaries 6.5 and 6.8, and Proposition 6.9). For every adjunction-universal machine VV, the set G(V)G(V) is co-c.e., its c.e. subsets obey a computable bound on their size, and hence it has no infinite c.e. subset, and it has intrinsic density zero. Conversely, for every finite set SS of strings there is a machine VV satisfying the three reference conditions with G(V)=SG(V)=S. For every such SS there is also a machine satisfying the three reference conditions for which the fixed-target connectivity problem is polynomial-time decidable for every target in SS and PSPACE-complete for every target outside SS.

If P differs from PSPACE, the last machine has polynomial-time fixed-target problems exactly for the targets in SS. Intrinsic density zero is the notion characterized by Astor through computable injective sampling [3]; the contribution here is that G(V)G(V) has it for every adjunction-universal machine VV, with an explicit rate (Theorem 6.6 and Corollary 6.8). Fix such a VV and a total computable injective list of strings, and let kk be the length of the one code, which depends on the list. Then for every q≥2q \ge2, at most a fraction O(2k/log⁡q)O(2^k/\log q) of the first qq entries lies in G(V)G(V). For an adjunction-universal machine VV with G(V)G(V) infinite, the computable bound makes G(V)G(V) effectively immune, meaning that a computable function of the index of a c.e. set bounds the size of every c.e. subset of G(V)G(V) (Proposition 6.9). Whether G(V)G(V) can be infinite for some adjunction-universal machine VV is open (Open Problem 2).

Our Techniques

The negative and positive results use the mandatory descriptions in opposite ways. The negative arguments count what every adjunction-universal machine must provide. The positive construction keeps those programs but controls when the other programs become available and how they attach.

Counting paths in the full cube. An adjunction-universal machine gives no control over programs outside the cylinder of a code, and any of them might help connect two descriptions. The negative arguments therefore count those programs instead of excluding them. A fixed linear-time source maps 0x0x and 1x1x to xx, and its code has some length dd. At program length m+d+1m+d+1, inside the cylinder of that code, its two mandatory descriptions of an mm-bit target xx are the only descriptions of xx. A simple path joining them therefore leaves the cylinder and has at least m+2m+2 vertices outside it.

Paths for different targets share no vertex, because one deterministic program has one output. There are only (2d−1)2m+1(2^d-1)2^{m+1} programs outside the cylinder of a code of length dd, so only a fraction O(2d/m)O(2^d/m) of the targets can have connected endpoints. The exceptional targets are defined through the untimed fiber, the graph with no deadline, so one exceptional set serves every later deadline.

To force many components rather than one disconnection, each target needs many mandatory descriptions that are pairwise far apart. A balanced linear map with well-separated preimage sets, built from finite-field parity checks adapted from the codes of Bose and Ray-Chaudhuri and of Hocquenghem [6, 12], supplies them. A traversal of a spanning tree shows that a connected subgraph of the cube containing k≥2k \ge2 terminals at pairwise distance at least DD has at least kD/2kD/2 vertices. Applied to each component in turn, this bound shows that most targets must have exponentially many components at length 2m+32m+3.

To reach exactly length 2m+32m+3, the source must know the length of its own code, which is chosen only after the source is fixed. The construction therefore supplies that length as a unary prefix of the raw input, so no source ever needs to compute its own code. Reed–Muller evaluation codes [4 Section 2.3] give a second family with an explicit tradeoff among program length, component count and the exceptional fraction.

The same balanced construction, tuned to a program length exponential in the target length, gives the threshold lower bound. The code of the source is still fixed across all those lengths, so most targets have a disconnected fiber at that length at every later deadline. Any threshold beyond which every fiber is empty or connected must therefore exceed that length.

Releasing a connected fiber at every deadline. The construction must make the fiber empty or connected at every deadline, not only when time is unlimited. A program needed on a connecting path might halt later than the descriptions it is meant to join, and at the intermediate deadlines the fiber could then be disconnected. The construction therefore admits a connected core first and lets simulated descriptions in only after the core is present.

The core rests on an explicit coloring of the cube of program bodies in which every color class is connected and every vertex has a neighbor of every color. It combines two syndrome registers with a selector bit; within each color class, paths to a fixed representative have linear length, and the coloring is computed on a schedule depending only on the body length. The syndrome part is the established coupon-coloring construction [8]; the connectedness of the classes and the fixed schedule are proved here. Each color is printed as a short string, and the strings printable at a given body length form its palette.

Programs have two mode bits. Core programs print the color of their body. In the two helper modes, the parity of the body decides whether a program prints its color, as a router, or runs the simulation, as a source helper. Every core and router program of one body length halts at one common time. Base programs and their matching source helpers run the same native simulation of a fixed base machine after a common delay, so they halt together, after the core and the routers are present. Every admitted program whose output lies in the current palette of colors therefore attaches to the core in at most three steps, which gives empty or connected fibers at every deadline and the diameter bound. The palette grows with the body length, and every fixed target eventually enters it, which gives a computable threshold exponential in the target length.

Uniform hardness uses targets outside the palette. No core or router program prints such a target, so its fiber contains only base programs and their source helpers, and each helper is a leaf attached to its base. A rigid code of a formula verifier in the parity-protected encoding then makes the base components with that code, after deleting their helper leaves, correspond exactly to the components of the solution graph of a formula. The reduction starts from the PSPACE-complete problem of connecting two satisfying assignments by single-variable changes [10].

The reduction picks the target before building the code, although the code length depends on the target. For a formula instance of encoding length LL, a target of length a fixed multiple of ⌈log⁡2(L+2)⌉\lceil\log_2(L+2) \rceil is long enough to lie outside the palette at the resulting body length, so only one verifier and one code are built. Membership in PSPACE uses Savitch’s recursive reachability method [18], with the native graph tests proved explicitly here.

Effective restrictions and finite hubs. To restrict G(V)G(V), the path count must be applied to many targets at once, although for general VV the paper gives no membership test for G(V)G(V), so the argument cannot rely on one. For a c.e. family of targets, one source machine waits for the indexed distinct elements of its enumeration and assigns each an antipodal pair of raw inputs. At each suffix length, the finitely many successful endpoints halt by a common deadline, whether or not that deadline can be computed. If all these targets lie in G(V)G(V), the outside-path count applies to all of them together. Choosing the suffix length from the code turns this into a computable bound on the size of c.e. subsets, and running the same source on a total injective list gives the density rate.

A fixed finite set SS reverses the order of quantifiers, since the machine may now depend on SS. Each target of SS gets a control header with a single one bit, which prints that target whatever suffix follows. The fiber of such a target therefore contains a whole cube of these hub programs before any base program halts, and every base program of the target differs from a hub program in one bit.

For targets outside SS, the fiber is empty at short lengths and early deadlines, and otherwise deleting the common base prefix is an exact isomorphism of fibers. The fiber of the base machine at deadline tt corresponds to the new fiber at deadline B+LtB + Lt, for constants BB and LL, so the fiber structure and the hardness of the base machine carry over. A sentinel keeps the shifted program’s left boundary during simulation, and all constants are computable from the base machine and SS. Interpretation is added last, by a new first transition that dispatches on the auxiliary input; on the empty auxiliary input the machine performs the old computation step for step, so no fiber changes (Lemma 3.25).

Other Related Work

The relevant precedents concern local-move output fibers, structural properties of decompressors, and the graph constructions used in the proofs. This subsection says what each establishes and how its setting differs from the one here.

Neutrality and description sets. Reidys, Stadler and Schuster develop configuration graphs and equal-image neutral sets [17 Sections 2 and 4 of the author preprint]. Their RNA compatibility graph also permits changes in two paired positions, so it does not coincide with the one-bit program graph in every case. Hu, Banzhaf and Ochoa use literal programs in a finite register-based model and study neutrality, search and phenotype transitions [11]. Schaper, Johnston and Louis study disconnected neutral components in RNA sequence maps under single point mutations [21 Section 2]. Equal-output mutation graphs of programs are therefore not new objects. The results here instead quantify over all adjunction-universal machines, or construct specific ones, with guarantees for the full set of descriptions at stated native deadlines, most of them holding at every later deadline.

Tadaki proves that the entire prefix-complexity function can stay unchanged while output-description cardinalities change [22 Theorems 4 and 9 of the final manuscript]. That is a close structural precedent, in a prefix-free optimal-machine model. Allender, Buhrman and Koucký construct machines retaining a universal machine by adjunction behind a fixed prefix while varying efficient reducibility properties of random-string sets [2 Theorem 14 of the author draft], so dependence on the machine under adjunction is also a precedent.

Bauwens, Kozachinskiy and Shen distinguish optimality from universality by adjunction and preserve plain complexity while installing the latter [5 Section 4, Proposition 1]; their questions concern plain complexity, which has no deadline. In that universality the string placed before the programs of a machine need only exist, with no time bound, whereas for an adjunction-universal machine the code is computable in polynomial time and the simulation has polynomial overhead. Milovanov shows that, for a suitable optimal plain decompressor, an oracle for description-length thresholds does not give a polynomial-time decision of the halting problem [15 Theorem 1.1]. These works concern minima, cardinalities or reductions to complexity predicates, whereas the results here concern connectivity of full fibers.

Coding, domination, and reachability. The finite-field checks adapt those of Bose and Ray-Chaudhuri and of Hocquenghem [6, 12]. The specific rank, balance and deterministic-construction properties needed in the packing proof are proved here. Reed–Muller evaluation codes provide the separated terminal family [4 Section 2.3].

Coupon coloring asks that every open neighborhood contain every color; Chen, Kim, Tait and Verstraete give finite-field constructions for cube colorings [8], and Goddard and Henning study the corresponding total-domatic and fractional formulations [GH18]. Connected domatic partitions are also established [23], and Shaw constructs linearly many completely independent spanning trees of the cube with linear diameter [Sha24, Theorem 1.2]. These general partition notions are known; the selector construction here is used for its connected color classes, its representative paths and its fixed native schedule.

The hardness reductions begin with the satisfying-assignment st-connectivity theorem of Gopalan, Kolaitis, Maneva and Papadimitriou [10 Theorem 2.9 and Section 3.3 of the full version]. That theorem concerns two supplied satisfying assignments, which is distinct from asking whether the whole solution graph is connected. General reconfiguration and its implicit-graph perspective are discussed by Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara and Uno [13] and surveyed by Nishimura [16].

Computability and parameterization. Astor characterizes intrinsic density through computable injective sampling [3 Corollary 4.3 of the accepted preprint]. Case discusses effective-immunity bounds and minimal-program sets in acceptable systems [7]. The statements about globally connected targets apply these established notions to a different set of outputs, with an explicit packing bound from one code. That G(V)G(V) is co-c.e. follows directly by enumerating finite witnesses of disconnected fibers.

Fixed-parameter tractability is standard, and so is the observation that a PSPACE-complete fixed-target connectivity problem at a constant parameter value rules it out unless P equals PSPACE. The content of the comparison here is the pair of machines satisfying the same reference conditions: one has a uniform target-parameter algorithm despite full PSPACE-completeness, while the rigid reference UU has a PSPACE-complete fixed-target connectivity problem.

Discussion

The numerical invariance theorem and fiber connectivity concern different data. A code controls what each program beginning with it computes and bounds its running time. It says nothing about adjacency between programs beginning with different codes, and it does not guarantee any path between the programs for one output.

Persistent fragmentation and eventual connectivity concern different program lengths. The fragmentation bounds hold at lengths chosen from the target length, while eventual connectivity holds from a threshold that depends on the target. For a machine with such thresholds, every length at which a fiber of a target is disconnected lies below the threshold of that target. The exponential lower bound on that threshold follows from a single disconnected fiber at an exponentially large length, which persists at every later deadline.

The shape of a fiber and the complexity of querying it are also separate. A disconnected fiber can still have a simple component test: for the machine of Theorem 1.3, most targets have disconnected fibers at some lengths (Theorem 5.5), yet every fixed target has a polynomial-time connectivity test (Corollary 5.3). Moreover, unless P equals PSPACE, polynomial-time connectivity for every fixed target need not give a uniform polynomial-time algorithm when the target varies. The construction of Theorem 1.3 exhibits both under adjunction and interpretation. It does not give a machine satisfying the reference conditions whose full connectivity language fails to be PSPACE-hard, and it does not classify such machines.

For globally connected targets, every finite set can be prescribed, with construction constants depending on that set. The packing obstruction instead uses one fixed code across unbounded suffix lengths. These quantifiers explain why finite prescriptions do not combine into an infinite computable family of globally connected targets for one adjunction-universal machine. The necessary conditions, co-c.e., computably bounded c.e. subsets and intrinsic density zero, are not known to suffice for an infinite realization.

Open Problems

We single out three questions. The first two stay within this native-fiber model and concern the full connectivity language under the reference conditions and the size of the set of globally connected targets. The third lets a path change the program length.

Complexity under the reference conditions. The fixed-target and parameterized separations do not decide whether the complexity of the full connectivity language is the same for every machine satisfying the reference conditions. reference conditions. The rigid reference and the machines of Theorems 5.4 and 6.2 have PSPACE-complete full connectivity languages.

Open Problem 1. Is Conn⁡(V)\operatorname{Conn}(V) PSPACE-complete for every machine VV satisfying all three reference conditions?

Here Conn⁡(V)\operatorname{Conn}(V) is the language of Problem 3.21, which always lies in PSPACE (Proposition 3.22). A negative answer therefore requires a machine meeting all three conditions whose full connectivity language is not PSPACE-hard.

Infinite globally connected-target sets. For every adjunction-universal machine VV, the packing bounds exclude every infinite c.e. subset of G(V)G(V) and force intrinsic density zero. Finite-hub completion realizes each finite set exactly, while later bridges cannot repair a disconnected fiber at an earlier deadline.

Open Problem 2. Does an adjunction-universal machine VV exist for which G(V)G(V) is infinite?

By Proposition 6.9, such a set would be co-c.e. and effectively immune.

Programs of all lengths. Every fiber studied in this paper has the programs of one length as vertices and one-bit flips as edges. Definition 3.19 also defines the edit graph, whose vertices are the programs of length at most a budget ℓ\ell that print xx within the deadline, and whose edges are flips, insertions and deletions of a single bit. Apart from its being an implicit graph (Lemma 3.20), so that its stst-connectivity problem lies in PSPACE, no result of this paper concerns it. Every fiber at a length at most ℓ\ell is an induced subgraph of that edit graph, but a path in the edit graph may change length, so neither fragmentation nor connectivity of the fibers carries over by itself.

The packing argument of Theorem 4.1 bounds the length of a path below by the Hamming distance of its endpoints, and in the edit graph only the edit distance bounds it. The two mandatory descriptions h0xh0x and h1x‾h1\overline{x} of that proof are at Hamming distance ∣x∣+1|x|+1, yet they can be at edit distance two as strings. For example, when x=(10)kx=(10)^k with k≥1k\ge1, deleting the bit after hh and then appending a 1 carries h0xh0x to h1x‾h1\overline{x}. This defeats only the lower bound used in that proof; it gives no path in the edit graph, since the intermediate string need not print xx.

Open Problem 3. Do an adjunction-universal machine VV and a computable function bb exist such that, for every target xx, every budget ℓ≥b(x)\ell\ge b(x) and every deadline tt, the edit graph of the programs of length at most ℓ\ell that print xx within tt native steps of VV is empty or connected?

A positive answer needs paths between programs of different lengths, and the proof of Theorem 5.2 does not address them, since it connects the programs of each length separately.

AI Disclosure

This work was developed with substantial assistance from Codex and Claude Code. These tools were used to discover almost all of the proofs in this work, find relevant literature, and write parts of the prose; the author wrote the rest. The author posed the problem, guided the development, and is responsible for any errors.

Paper Organization

Section 2 gives the preliminaries: strings, Hamming distance and the Boolean cube, native machines, adjunction, interpretation and full fibers. Section 3 supplies the explicit encoding and computational framework, including the numerical comparison of description lengths, defines the full connectivity language, and proves rigid-reference hardness and pointwise interpretation completion. Section 4 proves the first fragmentation bound for every adjunction-universal machine, the early separation between two machines satisfying the reference conditions, and sharper persistent fragmentation and component-multiplicity bounds. Section 5 constructs eventual connectivity, proves uniform hardness, establishes the exponential threshold obstruction, and derives the target-parameter consequences. Section 6 prescribes finite sets of easy targets and of globally connected targets, and proves effective restrictions on G(V)G(V) for every adjunction-universal machine.

Preliminaries

This section fixes the notation for strings, distances, graphs and the Boolean cube, the native machine model with adjunction and interpretation, and the full native fiber studied throughout.

Strings, Distances, and Cubes

References

  1. [1]Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  2. [2]Eric Allender, Harry Buhrman, and Michal Koucký. What can be efficiently reduced to the Kolmogorov-random strings? Annals of Pure and Applied Logic, 138(1–3):2–19, 2006.DOI
  3. [3]Eric P. Astor. Asymptotic density, immunity and randomness. Computability, 4(2):141–158, 2015. Accepted preprint arXiv:1405.0022v2, February 27, 2015; preprint numbering is identified where used.DOI
  4. [4]Emmanuel Abbe, Amir Shpilka, and Avi Wigderson. Reed–Muller codes for random erasures and errors. IEEE Transactions on Information Theory, 61(10):5229–5252, 2015. Author full version; Section 2.3 records the standard evaluation-code construction.
  5. [5]Bruno Bauwens, Alexander Kozachinskiy, and Alexander Shen. All Kolmogorov complexity functions are optimal, but are some more optimal?, 2025. arXiv:2506.16180 [cs.IT].arxiv.org/abs/2506.16180
  6. [6]R. C. Bose and D. K. Ray-Chaudhuri. On a class of error correcting binary group codes. Information and Control, 3(1):68–79, 1960. Original technical report: University of North Carolina Institute of Statistics, Mimeograph Series No. 240, September 1959.
  7. [7]John Case. Constructivity conditions on immune sets. Archive for Mathematical Logic, 64:819–841, 2025.DOI
  8. [8]Bob Chen, Jeong Han Kim, Michael Tait, and Jacques Verstraete. On coupon colorings of graphs. Discrete Applied Mathematics, 193:94–101, 2015. Preprint: arXiv:1404.6278v1.arxiv.org/abs/1404.6278
  9. [10]Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, and Christos H. Papadimitriou. The connectivity of Boolean satisfiability: Computational and structural dichotomies. SIAM Journal on Computing, 38(6):2330–2355, 2009. Full version: arXiv:cs/0609072v2.arxiv.org/abs/cs/0609072
  10. [11]Ting Hu, Wolfgang Banzhaf, and Gabriela Ochoa. How neutrality shapes evolution: Simplicity bias and search. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 1008–1016. ACM, 2025.DOI
  11. [12]Alexis Hocquenghem. Codes correcteurs d’erreurs. Chiffres, 2:147–156, 1959. Original article scan, ACONIT no. 26781; Section 6, pages 153–154.
  12. [13]Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12–14):1054–1065, 2011.
  13. [14]Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, fourth edition, 2019.
  14. [15]Alexey Milovanov. Limit on the computational power of C-random strings, 2026. arXiv:2605.16261v2 [cs.CC], May 19, 2026.
  15. [16]Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018.DOI
  16. [17]Christian Reidys, Peter F. Stadler, and Peter Schuster. Generic properties of combinatory maps: Neutral networks of RNA secondary structures. Bulletin of Mathematical Biology, 59(2):339–397, 1997. Author preprint: TBI Working Paper 95-07-04 (1995), Sections 2 and 4; this version is used for the configuration-graph and RNA-compatibility model comparison.pubmed.ncbi.nlm.nih.gov/9116604
  17. [18]Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970.DOI
  18. [20]Victor Shoup. A Computational Introduction to Number Theory and Algebra. Cambridge University Press, second edition, 2009. Author’s electronic Version 2, June 16, 2008, corresponding to the second print edition.
  19. [21]Steffen Schaper, Iain G. Johnston, and Ard A. Louis. Epistasis can lead to fragmented neutral spaces and contingency in evolution. Proceedings of the Royal Society B: Biological Sciences, 279(1734):1777–1783, 2012.
  20. [22]Kohtaro Tadaki. Properties of optimal prefix-free machines as instantaneous codes. In 2010 IEEE Information Theory Workshop (ITW), pages 1–5. IEEE, 2010.
  21. [23]Bohdan Zelinka. Connected domatic number of a graph. Mathematica Slovaca, 36(4):387–392, 1986.

Paper details

vlnc:W_mza2bcf6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Codex, Claude Code

View statement
Looking for related papers…
Contents