pith. sign in

arxiv: 2606.20399 · v1 · pith:U2LBWSNCnew · submitted 2026-06-18 · 💻 cs.CC

Linked Fates: How Small of an Ambiguity Increase Can Make the Difference Between Equaling and Separating from P?

Benjamin Carleton , Michael C. Chavrimootoo , Lane A. Hemaspaandra , David E. Narv\'aez , Conor Taliancich , Melissa Welsh This is my paper

Pith reviewed 2026-06-26 14:52 UTC · model grok-4.3

classification 💻 cs.CC
keywords ambiguity-bounded NPUP classesrelativizationoracle separationspath poisoningpaddingdeterministic simulation
0
0 comments X

The pith

For specific pairs of ambiguity functions, P equaling the lower-ambiguity UP class implies equality at the higher-ambiguity class even in all relativized worlds, while for most pairs this implication fails robustly.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies when equality between P and one ambiguity-bounded version of NP implies equality for a higher-ambiguity version. It identifies a new collection of function pairs where the implication holds robustly beyond the constant-ambiguity case already known from Watanabe. The positive cases are obtained by combining a path-poisoning construction that handles superconstant bounds with padding arguments. For essentially every other pair of bounds the paper shows that the implication does not hold robustly, by exhibiting oracles that separate the two classes while keeping the lower one equal to P.

Core claim

Theorem 3.8 gives a new class of pairs (f1, f2) with f1 ≤ f2 where P = UP_≤f1(n) implies P = UP_≤f2(n) holds in every relativized world; the proof relies on a path-poisoning technique (Theorem 3.5) that succeeds for some superconstant ambiguities together with padding (Theorems 3.3 and 3.4). For essentially all remaining pairs the implication fails to hold robustly.

What carries the argument

A path-poisoning construction that preserves polynomial-time deterministic simulation across relativized worlds while handling superconstant ambiguity bounds, used together with padding to enlarge the set of linked function pairs.

If this is right

  • For the function pairs identified in Theorem 3.8 the implication P = UP_≤f1 implies P = UP_≤f2 holds in every relativized world.
  • The linkage extends Watanabe's constant-ambiguity result to some superconstant cases.
  • For nearly all other pairs of nondecreasing functions there exists an oracle separating the two classes while keeping the lower one equal to P.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The boundary between linked and unlinked pairs is determined by the concrete growth rates that the path-poisoning construction can reach.
  • Further work could test whether the same pairs remain linked when the underlying machine model is changed from Turing machines to circuits.

Load-bearing premise

The path-poisoning technique can be applied to the identified superconstant function pairs while preserving the polynomial-time deterministic simulation in every relativized world.

What would settle it

An oracle relative to which, for one of the pairs covered by Theorem 3.8, P equals the lower-ambiguity class but is properly contained in the higher-ambiguity class.

read the original abstract

Ambiguity-bounded versions of $\mathrm{NP}$, denoted $\mathrm{UP}_{\leq f(n)}$, bound by $f(n)$ the number of accepting paths the nondeterministic polynomial-time Turing machine can have on inputs of length $n$. Such classes range from Valiant's completely unambiguous ($f(n)=1$) class $\mathrm{UP}$ to $\mathrm{NP}$ itself, where there is no bound or, equivalently, there is the toothless exponential bound ($f(n) = 2^{n^{O(1)}}$). This paper seeks to understand which of these classes stand and fall together as to whether they equal deterministic polynomial time. Informally put, what ranges of ambiguities have linked fates? That is, for which pairs of nondecreasing functions, $(f_1 ,f_2)$, satisfying $(\forall n)[f_1(n) \leq f_2(n)]$, does it hold that $\mathrm{P} = \mathrm{UP}_{\leq f_1(n)} \implies \mathrm{P} = \mathrm{UP}_{\leq f_2(n)}$. More particularly, for which pairs does that hold robustly, i.e., it holds in the real world and every relativized world? And for which pairs does that implication fail to hold robustly, i.e., there is an oracle $A$ such that $\mathrm{P}^A = \mathrm{UP}_{\leq f_1(n)}^A \subsetneq \mathrm{UP}_{\leq f_2(n)}^A$? The only previously known positive result is Watanabe's 1988 result that $ \mathrm{P} = \mathrm{UP}_{\leq 1} \implies (\forall k \geq 1)[\mathrm{P} = \mathrm{UP}_{\leq k}]$, which even holds robustly. His result, though lovely, applies only to constant-bounded ambiguities. As our positive result, we present a new class of cases (Theorem 3.8) that apply (and even robustly apply) at greater ambiguity levels. To give our class of cases, we leverage two approaches: a novel path-poisoning approach that works even on superconstant ambiguities (Theorem 3.5) and a new application of the power of padding (Theorems 3.3/3.4). As negative results, we show that for essentially all other cases, no linkage holds robustly.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies which pairs of nondecreasing functions (f1,f2) with f1(n)≤f2(n) satisfy the robust implication P=UP_≤f1 ⇒ P=UP_≤f2 (i.e., the implication holds in every relativized world). It presents a new class of positive cases (Theorem 3.8) that extend beyond constant ambiguities by combining a novel path-poisoning technique (Theorem 3.5) that works for superconstant ambiguities with padding arguments (Theorems 3.3/3.4). For essentially all other pairs it shows that the implication fails robustly via oracle separations.

Significance. If the central claims hold, the work provides a finer-grained picture of the ambiguity hierarchy relative to P, extending Watanabe's 1988 constant-ambiguity linkage to selected superconstant cases while establishing robust separations elsewhere. The path-poisoning and padding techniques are credited as novel contributions that enable the positive results.

major comments (2)
  1. [Theorem 3.5] Theorem 3.5 (path-poisoning): The construction must be shown to scale to superconstant f(n) while ensuring that any deterministic polynomial-time simulator for the lower-ambiguity class continues to work after oracle alteration, without the additional paths allowing new accepting computations that evade the simulation. The load-bearing claim in Theorem 3.8 that the implication holds robustly for the identified pairs rests on this preservation property.
  2. [Theorem 3.8] Theorem 3.8: The claimed class of positive cases is obtained by combining Theorems 3.3/3.4 (padding) with Theorem 3.5 (path-poisoning). It is necessary to verify that the path-poisoning applies to the specific superconstant function pairs without violating the polynomial-time deterministic simulation in every relativized world; if the poisoning is limited to a constant number of paths or requires oracle-query forms that fail for ω(1) ambiguities, the robust linkage does not hold for the stated class.
minor comments (2)
  1. [Abstract] The abstract and introduction should explicitly state the precise growth-rate conditions on f1 and f2 under which Theorem 3.8 applies, to make the scope of the positive result immediately clear.
  2. [Theorem 3.8] Notation for the function classes UP_≤f(n) is used consistently, but a brief reminder of the exact definition (number of accepting paths bounded by f(n)) in the statement of Theorem 3.8 would aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for identifying the key technical points on which the robust linkages rest. We respond point-by-point to the major comments.

read point-by-point responses

  1. Referee: [Theorem 3.5] Theorem 3.5 (path-poisoning): The construction must be shown to scale to superconstant f(n) while ensuring that any deterministic polynomial-time simulator for the lower-ambiguity class continues to work after oracle alteration, without the additional paths allowing new accepting computations that evade the simulation. The load-bearing claim in Theorem 3.8 that the implication holds robustly for the identified pairs rests on this preservation property.

    Authors: Theorem 3.5 gives an explicit oracle-relative construction that works for arbitrary nondecreasing f(n). The poisoning step alters only O(f(n)) paths per input length and is performed so that any new accepting path for a machine in UP_≤f1 must query a poisoned location; the simulator, being deterministic and polynomial-time, can be shown to reject on those queries by the same argument used for the constant case. The proof is carried out in the relativized setting and does not restrict the number of poisoned paths to a constant. We are happy to expand the write-up of the simulator-invariance argument if the current level of detail is insufficient. revision: partial

  2. Referee: [Theorem 3.8] Theorem 3.8: The claimed class of positive cases is obtained by combining Theorems 3.3/3.4 (padding) with Theorem 3.5 (path-poisoning). It is necessary to verify that the path-poisoning applies to the specific superconstant function pairs without violating the polynomial-time deterministic simulation in every relativized world; if the poisoning is limited to a constant number of paths or requires oracle-query forms that fail for ω(1) ambiguities, the robust linkage does not hold for the stated class.

    Authors: The function pairs identified in Theorem 3.8 are precisely those for which the growth rate of f2 relative to f1 permits the padding reductions of Theorems 3.3/3.4 to map instances while preserving the path-poisoning bounds of Theorem 3.5. The proof of Theorem 3.8 explicitly checks that the composed construction remains a valid relativized simulation: the deterministic polynomial-time machine for the lower-ambiguity class continues to work because the additional paths introduced by padding are poisoned in exactly the same manner as in the base construction. The argument is not restricted to constant ambiguity and applies directly to the superconstant pairs stated in the theorem. revision: no

Circularity Check

0 steps flagged

No circularity; derivation uses independent standard relativization techniques.

full rationale

The paper's positive results (Theorem 3.8) rest on explicit constructions: path-poisoning (Theorem 3.5) for superconstant ambiguities and padding arguments (Theorems 3.3/3.4). These are presented as novel but mathematically self-contained oracle techniques that do not reduce to fitted parameters, self-definitions, or load-bearing self-citations. The cited Watanabe 1988 result is external prior work establishing the constant case, and the negative results are separation oracles. No equation or claim equates a derived quantity to its input by construction; the chain is a standard proof of relativized implications and separations.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces no new free parameters or invented entities. It relies on standard background from complexity theory.

axioms (2)
  • standard math Standard definitions of polynomial-time Turing machines and relativized worlds preserve class inclusions and equalities
    Invoked throughout the setup of UP≤f(n) classes and the robust (relativized) implications.
  • domain assumption Nondecreasing functions f1 ≤ f2 define valid ambiguity bounds for the classes under study
    Stated explicitly in the problem formulation for the pairs considered.

pith-pipeline@v0.9.1-grok · 6024 in / 1451 out tokens · 38135 ms · 2026-06-26T14:52:40.069244+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 2 canonical work pages

  1. [1]

    Aaronson

    S. Aaronson. MIP ^* = RE . Shtetl-Optimized (the blog of Scott Aaronson), www.scottaaronson.com/blog/?p=4512 , 2020

    2020

  2. [2]

    Allender and R

    E. Allender and R. Rubinstein. P -printable sets. SIAM Journal on Computing , 17(6):1193--1202, 1988

    1988

  3. [3]

    Babai and L

    L. Babai and L. Fortnow. Arithmetization: a new method in structural complexity theory. Computational Complexity , 1(1):41--66, 1991

    1991

  4. [4]

    Baker, J

    T. Baker, J. Gill, and R. Solovay. Relativizations of the P =? N P question. SIAM Journal on Computing , 4(4):431--442, 1975

    1975

  5. [5]

    R. Beigel. On the relativized power of additional accepting paths. In Proceedings of the 4th Structure in Complexity Theory Conference , pages 216--224. IEEE Computer Society Press, June 1989

    1989

  6. [6]

    Beigel, December 15, 1993

    R. Beigel, December 15, 1993. Personal communication

    1993

  7. [7]

    Bellare and S

    M. Bellare and S. Goldwasser. The complexity of decision versus search. SIAM Journal on Computing , 23(1):97--119, 1994

    1994

  8. [8]

    Berman and J

    L. Berman and J. Hartmanis. On isomorphisms and density of N P and other complete sets. SIAM Journal on Computing , 6(2):305--322, 1977

    1977

  9. [9]

    Blum and R

    M. Blum and R. Impagliazzo. Generic oracles and ora\-cle classes. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science , pages 118--126. IEEE Computer Society Press, October 1987

    1987

  10. [10]

    R. Book. Tally languages and complexity classes. Information and Control , 26(2):186--193, 1974

    1974

  11. [11]

    Buhrman, L

    H. Buhrman, L. Fortnow, and T. Thierauf. Nonrelativizing separations. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity , pages 8--12. IEEE Computer Society Press, June 1998

    1998

  12. [12]

    Faliszewski and M

    P. Faliszewski and M. Ogihara. On the autoreducibility of functions. Theory of Computing Systems , 46(2):222--245, 2010

    2010

  13. [13]

    Fenner, L

    S. Fenner, L. Fortnow, and S. Kurtz. The Isomorphism Conjecture holds relative to an oracle. SIAM Journal on Computing , 25(1):193--206, 1996

    1996

  14. [14]

    Fortnow, September 2000

    L. Fortnow, September 2000. Personal communication

    2000

  15. [15]

    L. Fortnow. Worlds to die harder for: Open oracle questions for the 21st century. SIGACT News , 52(3):26--36, 2021

    2021

  16. [16]

    Fortnow and J

    L. Fortnow and J. Rogers. Separability and one-way functions. Computational Complexity , 11(3--4):137--157, 2002

    2002

  17. [17]

    Grollmann and A

    J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing , 17(2):309--335, 1988. https://doi.org/10.1137/0217018 doi:10.1137/0217018

    work page doi:10.1137/0217018 1988

  18. [18]

    Hartmanis

    J. Hartmanis. Feasible Computations and Provable Complexity Properties . CBMS-NSF Regional Conference Series in Applied Mathematics \#30. SIAM, 1978

    1978

  19. [19]

    Hartmanis, R

    J. Hartmanis, R. Chang, S. Chari, D. Ranjan, and P. Rohatgi. Relativization: A revisionistic retrospective. Bulletin of the EATCS , 47:144--153, 1992

    1992

  20. [20]

    Hartmanis and L

    J. Hartmanis and L. Hemachandra. Complexity classes without machines: O n complete languages for UP . Theoretical Computer Science , 58(1--3):129--142, 1988

    1988

  21. [21]

    Hartmanis and L

    J. Hartmanis and L. Hemachandra. Robust machines accept easy sets. Theoretical Computer Science , 74(2):217--226, 1990

    1990

  22. [22]

    Hartmanis and L

    J. Hartmanis and L. Hemachandra. One-way functions and the non-isomorphism of N P -complete sets. Theoretical Computer Science , 81(1):155--163, 1991

    1991

  23. [23]

    Hartmanis and N

    J. Hartmanis and N. Immerman. On complete problems for NP coNP . In Proceedings of the 12th International Colloquium on Automata, Languages, and Programming , pages 250--259. Springer-Verlag Lecture Notes in Computer Science \#194 , July 1985

    1985

  24. [24]

    Hartmanis, N

    J. Hartmanis, N. Immerman, and V. Sewelson. Sparse sets in N P - P : EXPTIME versus NEXPTIME . Information and Control , 65(2--3):159--181, 1985

    1985

  25. [25]

    Hemaspaandra, S

    L. Hemaspaandra, S. Jain, and N. Vereshchagin. Banishing robust T uring completeness. International Journal of Foundations of Computer Science , 4(3):245--265, 1993

    1993

  26. [26]

    Hemaspaandra, M

    L. Hemaspaandra, M. Juvekar, A. Nadjimzadah, and P. Phillips. Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting. ACM Transactions on Computation , 16(\#4, Article 20):1--26, 2024

    2024

  27. [27]

    Hemaspaandra and M

    L. Hemaspaandra and M. Ogihara. The Complexity Theory Companion . Springer-Verlag, 2002

    2002

  28. [28]

    Hemaspaandra, A

    L. Hemaspaandra, A. Ramachandran, and M. Zimand. Worlds to die for. SIGACT News , 26(4):5--15, 1995

    1995

  29. [29]

    Hemaspaandra and J

    L. Hemaspaandra and J. Rothe. Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory. Journal of Computer and System Sciences , 58(3):648--659, 1999

    1999

  30. [30]

    Hemaspaandra and M

    L. Hemaspaandra and M. Zimand. Strong forms of balanced immunity. Technical Report TR-480, Department of Computer Science, University of Rochester, Rochester, NY, December 1993. Revised, May 1994

    1993

  31. [31]

    Homan and M

    C. Homan and M. Thakur. One-way permutations and self-witnessing languages. Journal of Computer and System Sciences , 67(3):608--622, November 2003

    2003

  32. [32]

    Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen. MIP ^* = RE . Technical Report arXiv:2001.04383 [quant-ph], Computing Research Repository, arXiv.org/corr/ , January 2020

    work page arXiv 2001

  33. [33]

    K. Ko. On some natural complete operators. Theoretical Computer Science , 37(1):1--30, 1985

    1985

  34. [34]

    Lange and P

    K.-J. Lange and P. Rossmanith. Unambiguous polynomial hierarchies and exponential size. In Proceedings of the 9th Structure in Complexity Theory Conference , pages 106--115. IEEE Computer Society Press, June/July 1994

    1994

  35. [35]

    C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM , 39(4):859--868, 1992

    1992

  36. [36]

    C. Rackoff. Relativized questions involving probabilistic algorithms. Journal of the ACM , 29(1):261--268, 1982

    1982

  37. [37]

    A. Shamir. IP = PSPACE . Journal of the ACM , 39(4):869--877, 1992

    1992

  38. [38]

    Sheu and T

    M. Sheu and T. Long. UP and the low and high hierarchies: A relativized separation. Mathematical Systems Theory , 29(5):423--450, 1996

    1996

  39. [39]

    M. Sipser. On relativization and the existence of complete sets. In Proceedings of the 9th International Colloquium on Automata, Languages, and Programming , pages 523--531. Springer-Verlag Lecture Notes in Computer Science \#140 , July 1982

    1982

  40. [40]

    M. Sipser. Introduction to the Theory of Computation . Cengage Learning, 3rd edition, 2013

    2013

  41. [41]

    L. Valiant. The relative complexity of checking and evaluating. Information Processing Letters , 5(1):20--23, 1976

    1976

  42. [42]

    Vereshchagin

    N. Vereshchagin. Relativizable and nonrelativizable theorems in the polynomial theory of algorithms. Russian Academy of Sciences--Izvestiya--Mathematics , 42(2):261--298, 1994

    1994

  43. [43]

    Watanabe

    O. Watanabe. On hardness of one-way functions. Information Processing Letters , 27(3):151--157, 1988

    1988