Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?

arXiv:2610.25830 · cs.CC, math.PR · Submitted 2026-10-19 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Random Clocks on Computation Paths".

Paper summary: Tom: So wrapping up this look at "Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?". The authors explore how random clocks affect observation complexity by looking at forward, backward, and stationary moves on a computation path >

Jane: The authors are essentially showing that the ability to step back isn't a universal fix for exponential time problems; it only helps when the long jumps in the clock distribution are rare enough that they allow us to reach exponential time, but it doesn't help if those leaps completely ignore where we are on the path >

Lu: The paper highlights several specific clock families, like those with doubling gates or parity clocks, showing how different jump structures lead to different complexity bounds for forward-only versus backward-enabled observation >

Meng: If you were trying to design a real AI system based on this, you'd have to be really precise about the distribution of your random events; if your clock has too many long jumps at regular intervals, the benefit of stepping back disappears quickly when it comes to scaling up >

Lalam: It seems like they establish some concrete bounds on what one fixed computable law can achieve, showing that some laws have class exponential time and others are much slower, like two times O of log k n >

Tom: The overall implication is that the power of a random clock isn't just about being able to move backward; it’s about the specific structure of those moves relative to the computation path itself >

Jane: It also points toward open questions they mention, like sparse zero-drift laws and negative-mean laws with only some finite positive moments, suggesting there are still areas where we don't fully understand these bounds >

Conclusion: Tom: So we're wrapping up our look at this paper, "Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?". Basically, they're figuring out how much you can observe a deterministic math path if your clock is random and can move forward, backward, or stay still.

Jane: I mean for someone just listening to the drive or cooking—what does that actually mean in practice? Is this about building better computers or something else?

Tom: It's about the limits of observation complexity. The main thing they show is that you can use these random clocks to recognize languages if you allow polynomial observations, but stepping backward on the clock can push that recognition power way up to exponential time in some cases.

Lu: That's the core idea—that the structure of those clock jumps matters a lot. If the long jumps are rare, stepping back helps you get there exponentially; if they ignore your position, it doesn't matter at all.

Meng: From a deployment angle, that means if your random process has predictable long moves, you need to be careful about how you structure those moves on the path if you want to keep things manageable and not run into exponential scaling issues.

Lalam: I see a lot of specific results here too. For instance, they show that for certain independent jumps, one fixed computable law ends up having an exponential time complexity class, while others are much faster, like two times O of log k n.

Jane: So what does this change for the people listening who don't read math? It sounds like it shows that even simple random movement can have deep consequences for how hard a problem is to solve.

Tom: It means we have to be super precise about the rules of our random processes, because a tiny change in those jump probabilities—like adding just one step backward—can fundamentally change whether you're stuck in polynomial time or climbing into exponential time complexity.

Lu: The authors also touched on some open questions about very sparse laws and negative mean laws, suggesting there are still big gaps in what we understand about these bounds.

Jane: It's a lot of data here, but it points to the fact that even seemingly random processes have hard limits on how much they can compute before they hit exponential walls. This leads us perfectly into how specific clock families behave when you look at the confidence level of your observations.

Amirkabir University of Technology

cs.CC, math.PR

Submitted: 2026-10-19

Updated: 2026-11-17

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: The paper investigates the observation complexity resulting from using a random clock that can move forward, backward, or stay in place when observing a fixed deterministic computation path.

Key concepts

Forward-only clocks
These clocks only allow movement in the positive direction. The paper finds that if large forward moves happen infrequently, a forward-only clock cannot exceed polynomial time. However, even a single step backward can significantly increase the recognition power to exponential time.
Backward access utility
Stepping back is vital for increasing recognition power when long jumps are rare. If the clock's large leaps ignore its current position, stepping back provides a decisive advantage in raising the complexity class to exponential time.
Independent Jumps
When jumps are independent, the reach of a clock is bounded by comparing proposals. This leads to specific results: one fixed computable law has class EXP, while others have classes like DTIME(2O(log k n) or 2EXP).
Negative Drift
A negative drift with positive forward probability and finite positive moments guarantees recognition of reverse-definite languages. This is a specific result showing how certain clock behaviors directly map to language classes.

Terminology

Summary

The paper investigates the observation complexity resulting from using a random clock that can move forward, backward, or stay in place when observing a fixed deterministic computation path. p. 1

Where the paper says it

As a first step in this formulation, we study one perspective: stochastic access to a fixed deterministic computation path and the resulting observation complexity. A random clock selects indices by moving forward, backward, or remaining in place.

The central theme revolves around determining which jump laws and position-dependent kernels allow polynomially many observations to recognize languages, and specifically when backward access enhances this recognition power beyond what is achievable with purely forward clocks. p. 1
Where the paper says it

For a fixed random clock, the probability of reaching a threshold within q ticks determines the languages recognisable at confidence α (Theorem 2. We ask which jump laws and position-dependent kernels let polynomially many observations recognise which languages, and when backward access enlarges this power beyond every comparable forward-only clock in a specified family.

Key findings regarding the reach of such clocks are detailed:

  • Forward-only clocks: If the long leaps occur only at rare positions, no forward-only clock can exceed polynomial time. However, even a single step back can raise the reach to exponential time. p. 0

    Where the paper says it

    For clocks whose long leaps occur only at rare positions, no forward-only clock goes beyond polynomial time, while even single steps back raise the reach to exponential time. Stepping back cannot help, however, when the clock’s leaps ignore its position.

  • Backward access utility: Stepping back is decisive when long leaps are rare; it raises the reach to exponential time. Conversely, stepping back cannot help if the clock's leaps ignore its position.

  • Specific Clock Families: For clocks whose only large forward moves are doublings at powers of two, a forward-only clock remains in P, but steps back by one (confined to indices of density zero with vanishing probability) yield EXP. A fixed-return gated clock maintains a crossing budget related to 2 T. p. 2

    Where the paper says it

    18) In a family whose only large forward moves are doublings at powers of two, every forward-only clock has class within P, whereas steps back by one, confined to a set of indices of density zero and possibly with vanishing probability, give EXP. The fixed-return gated clock has crossing budget (1 + o(1))(1 + β −1 )log2 T at every confidence.

  • Independent Jumps: For independent jumps, the reach R alpha(q) is bounded between the alpha-quantile of the largest of q proposals and q times that quantile. This implies that one fixed computable law has class exactly EXP, while for each k at least 1, one fixed computable law has class DTIME(2O(k n)), and another has class 2 EXP. p. 3

    Where the paper says it

    8) For independent jumps the reach Rα(q) lies between the α-quantile of the largest of q proposals and q times that quantile. Consequently one fixed computable law has class exactly EXP; for each k ≥ 1 one fixed computable law has class exactly QPk = DTIME(2O(logk n) ); and one fixed computable law has class 2EXP.

The paper examines several specific results:

  • Negative Drift: A negative drift with positive forward probability and all positive moments finite yields exactly the reverse-definite languages (Theorem A).

  • Parity Clocks: The parity example demonstrates a gain over deletion, where forward re-entry also attains EXP (Theorem 6.6). In the gated family, every forward-only clock stays in P, but length-one returns attain EXP or 2 EXP (Theorem 6. p. 2

    Where the paper says it

    18) In a family whose only large forward moves are doublings at powers of two, every forward-only clock has class within P, whereas steps back by one, confined to a set of indices of density zero and possibly with vanishing probability, give EXP. The fixed-return gated clock has crossing budget (1 + o(1))(1 + β −1 )log2 T at every confidence.

    13).

  • Backward Moves and Class Transitions: If the forward displacement law is stochastically nondecreasing in position, deleting backward moves does not lower the class. For a parity-dependent clock, a single step back reopens a heavy-sampling phase, causing the class to rise from P to EXP and reducing the crossing budget. p. 2

    Where the paper says it

    11) If the forwarddisplacement law is stochastically nondecreasing in position, deleting backward moves never lowers the class. For a parity-dependent clock, a step back by one reopens a heavy-sampling phase: the class rises from P to EXP and the crossing budget falls from (1 + o(1))T to (1 + o(1))(1 + β −1 )ℓα log2 T, where ℓα = − ln(1 − α).

  • Reach Bounds (Theorem D): For independent jumps, specific computable laws are shown to have classes EXP and 2 EXP.

The analysis also delves into open problems concerning sparse zero-drift laws and negative-mean laws with only some finite positive moments. p. 3

Where the paper says it

QP2 P = QP1 one zero-drift class and a negative-drift antichain Theorems 4. 8 RDEF {∅, Σ ∗ } ⊊ ⊊ ⊊ ⊊ ⊊ ⊊ ⊊ ⊊ ⊆ busy-beaver law computable laws (union) K = 22 J ; squaring gates µE; parity ηβ; gated η gate β µ[k] positive drift / regular nondegenerate zero drift sparse laws negative drift, all positive moments frozen law forwardonly gated clocks stay here Figure 2: The landscape of observation classes.

The results indicate that sparse computable constructions yield one intermediate zero-drift class below P, while an infinite negative-drift antichain exists below P (Theorem 4. p. 3
Where the paper says it

QP2 P = QP1 one zero-drift class and a negative-drift antichain Theorems 4. 8 RDEF {∅, Σ ∗ } ⊊ ⊊ ⊊ ⊊ ⊊ ⊊ ⊊ ⊊ ⊆ busy-beaver law computable laws (union) K = 22 J ; squaring gates µE; parity ηβ; gated η gate β µ[k] positive drift / regular nondegenerate zero drift sparse laws negative drift, all positive moments frozen law forwardonly gated clocks stay here Figure 2: The landscape of observation classes.

6).

Further analysis in Appendix F focuses on common budgets over parameter sets for various clock families:

  • Confidence Dependence: For position-dependent kernels, the class depends on the confidence level alpha: C zeta, alpha = EXP for 0 < alpha < 1/2, and C zeta, alpha = P for 1/2 at most alpha < 1 (Remark E.7).

  • Common Budgets: Theorem F.3 establishes that for the activation family, if the infimum of allowed backward probabilities b* is greater than zero, then UB alpha = EXP; if b* = 0, then UB alpha = P. p. 2

    Where the paper says it

    Theorem B (Backward moves are necessary, and may be sparse; Theorems 6. 18) In a family whose only large forward moves are doublings at powers of two, every forward-only clock has class within P, whereas steps back by one, confined to a set of indices of density zero and possibly with vanishing probability, give EXP.

    This is based on the criterion depending on the set's infimum.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved reachability analysis for random clock models allows systems to determine if a given language belongs to classes like P or EXP by analyzing crossing probabilities against observation budgets, specifically using Theorem 2.18 which states that "If Rα(q) ≤ C(q + 1)d for finite C, d > 0, then Cα ≤ P."

  2. Enhanced decision-making for languages with sparse zero-drift laws allows systems to recognize languages outside the reverse definite class by constructing computable laws where AMe,j0(x) ≤ C(n + 2) log2(n + 2) for a constant C independent of both e and j0.

  3. Systems can distinguish between polynomial and exponential time complexity classes in gated families by analyzing the necessary role of backward moves, as Theorem 6.13 states that In this family, every forward-only clock stays polynomial, whereas a step back accesses exponential time.

  4. Advanced reasoning systems can exploit phase reuse in parity clocks to transition from polynomial time to exponential time by leveraging the fact that A length-one return changes the parity clock’s class from P to EXP (Theorem 6.6).

  5. Systems can classify iid laws into infinitely many pairwise incomparable classes below P by utilizing sparse negative-drift laws, as Theorem 4.8 demonstrates that L(e)j0 ∈ / P∗µ⟨e′⟩,α' for e′ != e.

  6. A new computational model can be designed to recognize semidecidable languages (RE) using a noncomputable law where The witnessing law may depend on the language (Theorem 5.11), providing a theoretical framework for recognizing undecidable languages.

Abstract

A lookup, a prediction, or a return to a saved state can bring us to a stage of a computation without replaying the intervening steps. We model this access by a random clock, fixed in advance, that moves along a deterministic computation by jumping forward or stepping backward. Each observation costs one unit. We ask which language classes can be recognized with polynomially many observations. For clocks with independent jumps, the resulting class depends primarily on the tail of the forward-jump distribution. We give explicit clocks that recognize exactly EXP, 2EXP, and each quasipolynomial class QP k, with the latter forming a strict hierarchy between P and EXP. A backward-drifting clock with sufficiently rare long forward jumps recognizes exactly the reverse-definite languages, whose membership is determined by a bounded prefix of the input. Between the reverse-definite languages and P, we construct infinitely many pairwise incomparable classes. Finally, we construct families in which every forward-only clock recognizes only languages in P, while allowing occasional one-step backward moves yields EXP and larger classes.

Related papers