Pith. sign in

REVIEW 5 major objections 4 minor 68 references

Phase Transitions in Decision Problems Over Odd-Sized Alphabets

T0 review · 5 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that every adequately-balanced language over an odd-sized alphabet exhibits a phase transition, so together with the even case every adequately-balanced language does.

desk verdict Odd-alphabet extension is a natural question, but the P-isomorphism bridge is broken, so the theorem is unsupported. read the letter →

arxiv 2505.09282 v1 pith:CBTSTTKZ submitted 2025-05-14 cs.CC

Andrew Jackson This is my paper · ORCID
classification cs.CC
keywords phasetransitionsindecisionproblemsodd-sizedalphabetsadequately-balancedlanguagespaddableP-isomorphismnot-anywhere-exponentially-unbalancedRoughPcomputationalcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to close a parity gap in the theory of phase transitions in decision problems. It claims that every 'adequately-balanced' language over an odd-sized alphabet has a phase transition, meaning there is a polynomial-time parameter along which the accepting fraction tends to 1 in one direction and to 0 in the other, with exponentially concentrated parameter slices near a threshold. Since an earlier result already covered even-sized alphabets, the two claims together imply that every adequately-balanced language over every finite alphabet of at least two symbols exhibits a phase transition. The argument works by mapping the odd alphabet to an even alphabet one symbol larger, transferring the language to the even side, and carrying the phase transition back.

What carries the argument

The load-bearing object is the preserving P-isomorphism $\xi=\alpha_\Pi\circ\theta_\Sigma$. Here $\theta_\Sigma$ reads a string over the odd alphabet as an integer in little-endian base $|\Sigma|$, and $\alpha_\Pi$ writes that integer as a word over $\Pi$ in base $|\Pi|=|\Sigma|+1$. A preserving P-isomorphism is a polynomial-time bijection between the two string sets that preserves membership in the corresponding languages, so $\xi$ converts the odd-alphabet language into an even-alphabet language while keeping 'is accepted' unchanged. Because the map is bijective and fast, parameter slices, acceptance fractions, and exponential-growth conditions are carried across in both directions, which is what lets a phase transition on the even side be imported back to the odd side. The additional clauses in the definition of 'adequately-balanced' for odd alphabets are engineered to make the transferred even-alphabet language satisfy the known sufficient conditions.

What would settle it

Compute the proposed map on one small input: take $\Sigma=\{1,2,3\}$ and $\Pi=\{1,2,3,4\}$, and let $x='121'$. The little-endian base-3 value is $1+2\cdot 3+1\cdot 9=16$, and the paper's output rule expresses 16 in base 4 as '001', which contains the symbol 0 and therefore is not a word over $\Pi$. This single calculation shows $\xi$ is not a map from $\Sigma^*$ to $\Pi^*$ as written; if no corrected digit convention is supplied, the reduction has no first step.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 2: any adequately-balanced language over an odd-sized alphabet exhibits a phase transition. The theorem is proved by reduction to the already-established even case. Given an adequately-balanced language $L$ over $\Sigma$ with $|\Sigma|$ odd, the author constructs a preserving P-isomorphism $\xi:\Sigma^*\to\Pi^*$, where $|\Pi|=|\Sigma|+1$ is even, and defines $H=\{\xi(x): x\in L\}$. The proof then tries to show $H$ is paddable and not-anywhere-exponentially-unbalanced, which makes Theorem 1 applicable, and finally uses the fact that membership-preserving bijections push phase transitions forward to conclude $L$ has one. Combined with Theorem 1, this yields Theorem 3: every adequately-balanced language exhibits a phase transition.

Load-bearing premise

The proof rests on a 'P-isomorphism,' a fast and reversible renaming that maps every string over the odd alphabet to a string over the even alphabet. That renaming must actually be reversible and land inside the target alphabet; the proposed rule writes numbers using symbols 1 through $|\Sigma|$ but decodes them using digits 0 through $|\Pi|-1$, so the two digit conventions do not line up.

Editorial extensions

If this is right

  • Phase transitions in decision problems cannot be blamed on alphabet parity: every adequately-balanced language over every alphabet of size at least two has one.
  • The preservation argument supplies a transfer principle: any phenomenon that is provably present for all even-sized alphabets and is invariant under preserving P-isomorphisms will automatically be present for odd-sized alphabets.
  • For paddable promise-BQP languages, the phase transition is available as a heuristic check on a quantum device's outputs, the setting sketched in the paper's proposed verification protocol.
  • Because no paddable language is sparse, the balanced-density requirement does not silently restrict the theorem to a trivial or empty class of languages.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof is existential: it does not exhibit the threshold parameter for any specific language, so actually using these transitions to test or accredit an algorithm would require a separate construction for the parameter.
  • If the digit mismatch in $\xi$ is repaired by giving both alphabets the same digit convention, the overall strategy could go through; if it cannot be repaired, the odd-alphabet theorem needs a different reduction than the one presented.
  • A natural testable next step is to relax the odd-alphabet extra conditions one by one and ask whether the phase transition persists, since the author himself flags those conditions as proof artifacts rather than fundamental restrictions.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 4 minor

Summary. The paper claims to extend the author's earlier result on phase transitions in decision problems over even-sized alphabets to odd-sized alphabets. It defines a class of languages called 'adequately-balanced' languages, states a definition of phase transitions for decision problems, and proves Theorem 2: every adequately-balanced language over an odd-sized alphabet exhibits a phase transition. Combined with the prior even-alphabet result, this yields Theorem 3: every adequately-balanced language exhibits a phase transition. The main technical bridge is Lemma 2, which proposes a polynomial-time bijection between strings over an alphabet of size |Σ| and strings over an alphabet of size |Σ|+1, and Lemma 3, which uses this bijection to reduce odd-alphabet languages to even-alphabet languages. Lemma 6 is then used to transfer the phase-transition property back along the bijection.

Significance. If the main theorem were correct, it would fill a genuine gap in the author's prior work and strengthen the claim that phase transitions are ubiquitous in decision problems. The paper also takes a natural high-level approach: transfer phase transitions along preserving-P-isomorphisms. However, the significance of the claimed result is undermined by load-bearing technical errors: the central encoding of Lemma 2 is not a bijection, Lemma 6's transferred parameter is not well-typed, and the formal definition of phase transition has an undefined 'fraction of Σ*' in condition 3. The paper currently does not provide a valid proof of its central claim.

major comments (5)
  1. [Appendix B.1, Lemma 2 and Defs. 18-20] The proposed mapping ξ is not a function from Σ* to Π*. Definition 18 interprets strings with symbols 1,...,|Σ| as base-|Σ| numerals, while Definition 19 outputs ordinary base-|Π| digits, which include 0. For Σ={1,2,3}, the word x='121' satisfies θ_Σ(x)=1·3^0+2·3^1+1·3^2=16, and α_Π(16) in base 4 is the string '001', which contains the symbol 0 not in Π. Thus ξ(x) is not a word over Π. Consequently H={ξ(x): x∈L} in Lemma 3 is not a language over Π, and the reduction to the even-alphabet theorem collapses.
  2. [Appendix B.1, Eq. (B6)] The algebra used to prove that α_Ξ(θ_Ξ(z)) recovers z is invalid: the sum contains terms |Ξ|^{j-k} with j<k, and negative powers are not handled by the stated modular arithmetic. Dropping the outer floor and claiming the result equals the k-th symbol of z is not justified. This is not a minor typo; it is the formal core of the attempted proof that ξ is invertible.
  3. [Appendix B.2, Lemma 6, Eq. (B48)] The transferred parameter γ' is ill-typed. Since γ maps Π* to R and ξ maps Σ* to Π*, the expression (ξ∘γ)(x) is undefined: ξ cannot be applied to a real number. The intended definition must be γ'(x)=γ(ξ(x)), and indeed the subsequent equation (B49) uses that correct form. As written, the definition of the parameter that is supposed to induce the phase transition in L does not make sense.
  4. [Section I.C, Def. 8, condition 3] Condition 3 of the phase-transition definition refers to 'the fraction of Σ*' that maps into a real interval, but Σ* is infinite and no probability measure is specified. Without a measure, this fraction is undefined, so the exponential-growth condition is not meaningful. This issue is inherited from the prior work but is load-bearing for both Theorem 1 and Theorem 2, since both are stated in terms of Definition 8.
  5. [Section II.A, Def. 16] The odd-alphabet portion of the definition of 'adequately-balanced' is not self-contained. Item 1 refers to sets defined using ξ and ξ^{-1} 'as in Def. 20', but Definition 20 appears only inside the proof of Lemma 2, which is supposed to establish the existence and correctness of ξ. If Lemma 2 fails, the definition of adequately-balanced over odd alphabets is underspecified, and even the statement of Theorem 2 lacks a clear domain of quantification.
minor comments (4)
  1. [Fig. 2 caption] The caption states that 1_H is the indicator function of H with domain Σ*, but H⊆Π*; the domain should be Π*.
  2. [Section II.C, proof of Theorem 2] The proof says Theorem 2 'depends most crucially on Theorem 1', but the actual dependence is on the validity of Lemmas 3 and 6; the phrasing obscures where the proof can fail.
  3. [Appendix B.2, Eq. (B29)-(B32)] The diagram-chasing argument in Fig. 5 is not a substitute for a precise proof of the claimed correspondence between the B_ϕ_j and B^{ξ^{-1}∘ϕ∘ξ}_n sets; the displayed equations do not by themselves establish contiguity or the claimed α_j values.
  4. [Throughout] There are numerous distracting typographical and referencing errors, including footnote markers that interrupt sentences and captions that do not match the text; a careful editorial pass is needed.

Circularity Check

2 steps flagged · score 7.0 of 10

The odd-alphabet phase-transition claim is substantially forced by Def. 16's alt-NAEU requirement plus the author's self-cited Theorem 1; the NAEU property that triggers the prior theorem is assumed, not derived.

  1. self definitional [Def. 15 (alt-NAEU), Def. 16 (odd additional requirement 3), Appendix B.1 Lemma 3 proof (paragraph 'His not-anywhere-exponentially-unbalanced')]
    "If the above holds for a paddable language when “P” is replaced by any RoughP algorithm constructed by applying a preserving-P-isomorphism – to a paddable language over an alphabet larger, by one, than the current alphabet – to the input string so that a RoughP algorithm for the new language – constructed as in Ref. [26] – can be applied, I call the language alt-NAEU. ... For languages where |Σ| is odd, there are additional requirements. ... 3. The language is alt-NAEU. ... The first step to bounding the right-hand-side of Eqn."

    The odd-sized case of 'adequately-balanced' is defined to include alt-NAEU, and alt-NAEU is defined as the condition that, after applying a preserving-P-isomorphism to an alphabet larger by one (which, for odd |Σ|, is even), the induced language satisfies the NAEU inequalities. In Lemma 3, the proof that the even-alphabet image H is not-anywhere-exponentially-unbalanced does not derive this from a weaker property; it explicitly invokes the third additional property of Def. 16 and then uses alt-NAEU to obtain the bound |B_j^φ ∩ L ∩ Ξ_L| ≥ Poly(j)^{-1}|B_j^φ|. That bound is exactly the NAEU condition for H transported through ξ.

  2. self citation load bearing [Sec. II C Proof of Theorem 2; Theorem 1 (Ref. [16])]
    "However, the proof of Theorem 2 depends most crucially on Theorem 1, and uses the phase transitions in paddable not-anywhere-exponentially-unbalanced language over an even-sized alphabets to construct phase transitions in the equivalent languages over odd-sized alphabets via preserving-P-isomorphisms. ... As H is a paddable not-anywhere-exponentially-unbalanced language over an even-sized alphabet, Theorem 1 implies that H exhibits a phase transition."

    The decisive step 'H is NAEU over an even-sized alphabet, therefore H exhibits a phase transition' is imported verbatim from Ref. [16], the same author's prior arXiv paper, and the current paper gives no proof or independent verification of Theorem 1. Since the NAEU condition on H is itself an assumption built into Def. 16 (see the first step), the odd-alphabet theorem reduces to applying a self-cited theorem to a definitionally supplied premise. This is load-bearing self-citation: the new result inherits its phase transition from the author's earlier theorem rather than establishing it independently for odd alphabets.

full rationale

Under the circularity rubric, the main issue is not the base-encoding defect in Lemma 2 (that is a correctness flaw, not a circularity), but the way 'adequately-balanced' is defined for odd alphabets. Def. 15 defines alt-NAEU as the property that, after applying a preserving-P-isomorphism to a language over an alphabet enlarged by one, the induced language satisfies the NAEU inequalities. Def. 16 then makes 'the language is alt-NAEU' one of the three additional requirements for odd-sized adequately-balanced languages. In Lemma 3, the proof that H is not-anywhere-exponentially-unbalanced does not derive this from a weaker condition; it explicitly invokes the third additional property of Def. 16. Thus the key NAEU fact that makes Theorem 1 applicable is an assumption written into the hypothesis. The proof also transfers paddability and the phase transition through ξ, and those transfers are legitimate (modulo the correctness of ξ), but they do not supply the phase transition itself; the phase transition comes from the self-cited Theorem 1. Consequently, Theorem 2 is close to being a restatement of 'odd alt-NAEU languages are isomorphic to even NAEU languages, which phase-transition by Theorem 1', with the isomorphism half given by definition. This is a partial self-definitional circularity, and the load-bearing prior theorem is also a self-citation. Score 7 reflects that the conclusion is substantially forced by definition plus self-citation, though phase transition is not literally written into Def. 16 and some transfer work is done by Lemmas 3 and 6.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no fitted parameters and no new physical or mathematical entities; it introduces only formal definitions (adequately-balanced, alt-NAEU) and relies on the author's prior theorem plus several unformalized technical assumptions.

assumptions (5)
  • domain assumption Theorem 1 of Ref [16]: any paddable not-anywhere-exponentially-unbalanced language over an even-sized alphabet exhibits a phase transition.
    Invoked without proof in Sec. II.C as the engine of the odd-alphabet result; it is the author's own prior theorem and is not independently verified here.
  • domain assumption Def. 8's notion of a phase transition is well-defined, including Condition 3's 'fraction of Σ*'.
    The fraction of the infinite set Σ* lying in a real interval is not mathematically specified; Lemma 6 relies on treating it as a meaningful quantity that is preserved under bijections.
  • ad hoc to paper The 'split proportionately' requirement (Def. 16, odd-alphabet item 1) is well-defined and the 'continuous subset' notion is meaningful.
    This condition is introduced to make the transfer argument work, but is never formalized; it is needed for Eq. B21.
  • ad hoc to paper The contiguity and order-preservation properties used in Lemma 4 hold for the constructed ξ.
    The proof asserts these informally (footnotes 51-52) and uses them to bound χ_upp(n) in Eq. B43; no formal proof is given.
  • ad hoc to paper The class of adequately-balanced languages over odd alphabets is nonempty.
    The paper only gives example polynomials Poly satisfying Eq. 8 (Eq. 9), not an actual language meeting all three additional requirements of Def. 16.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Phase Transitions in Decision Problems Over Odd-Sized Alphabets." pith.science (2026). https://pith.science/paper/CBTSTTKZ

@misc{pith2026250509282,
  author       = {Pith},
  title        = {Pith review of: Phase Transitions in Decision Problems Over Odd-Sized Alphabets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CBTSTTKZ}},
  note         = {Machine review of arXiv:2505.09282}
}
read the original abstract

In [A. Jackson, Explaining the ubiquity of phase transitions in decision problems (2025), arXiv:2501.14569], I established that phase transitions are always present in a large subset of decision problems over even-sized alphabets, explaining -- in part -- why phase transitions are seen so often in decision problems. However, decision problems over odd-sized alphabets were not discussed. Here, I correct that oversight, showing that a similar subset of decision problems over odd-sized alphabets also always exhibit phase transitions.

Figures

Figures reproduced from arXiv: 2505.09282 by the authors.

Figure 1
Figure 1. FIG. 1. [From Ref. [ [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Diagrams of the situation constructed in Lemma [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. Diagram of the situation constructed in Lemma [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: FIG. 4. A diagram entirely entailed by the lower half, which follows from both [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5. Diagram used in the proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6. Diagram of the situation in Lemma [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

68 extracted references · 61 canonical work pages

  1. [1]

    Asn−→ ∞,A[S γ n]−→1, with a monotonically in- creasing lower bound

    work page

  2. [2]

    Asn−→−∞,A[S γ n]−→0, with a monotonically de- creasing upper bound

    work page

  3. [3]

    The fraction ofΣ ∗ that takes a value ofγbetween A∈ R+ and A+δ(whereδ∈R +) grows exponentially [24] as|A -T|increases (whereT∈Ris a specific value). It may be useful to note that the above definition of phase transitions doesnotrequire the change in acceptance fraction happen while the parameter transitions through an interval (of the real numbers) of a s...

    work page

  4. [4]

    This can occur, however, only for at most an exponentially small fraction of strings

    Besides Accept/Reject,Pmay output another symbol, ⊥, meaning it is unable to decide if the input is in the language. This can occur, however, only for at most an exponentially small fraction of strings. I.e. there is a constantc∈[0,1) such that:∀n∈N, |Bϕ n∩{x∈Σ ∗|P(x)=⊥}| |Bϕ n| ≤c n,(7) whereB ϕ n is as in Def. 12. Thekey relevant result from previous wo...

    work page

  5. [5]

    The distribution of elements ofB ϕ n ⊂Σ ∗ that are both in and not in the language are split proportion- ately between the subsets in differingξ −1Bξ−1◦ϕ◦ξ n – so as to maintain the not-anywhere-exponentially- unbalanced property of each continuous subset – (with different values ofn∈N 0), whereξis as in Def. 20. 2.Polyis monotonically increasing and,∀n∈N...

    work page

  6. [6]

    Example Functions Meeting the Requirements ofPoly The condition in Eqn

    The language is alt-NAEU. Example Functions Meeting the Requirements ofPoly The condition in Eqn. 8 for the required polynomial,Poly, is met if: Poly(n)=βn+γ,(9) whereβ,γ∈R + such thatγ≥4β. B. Statement of Results The main focus of the present paper is to prove Theorem 2. Theorem 2.Any adequately-balanced language over an odd- sized alphabet exhibits a ph...

    work page

  7. [7]

    Construct a set,P p, of instances of a valid input to the problemPexpected to experience comparable error – during the execution of the circuit to decide it on the BQP-device – top

    work page

  8. [8]

    Use a phase transition ofPto obtain solutions,{S ′ j} |Pp| j=1 predicted by it, and corresponding confidences, {C j} |Pp| j=1, for each instance inP p

    work page

Show all 68 references
  1. [9]

    Call the outputs{S j} |Pp| j=1 and assumeS 0 is the BQP-device’s solution top

    Execute the – potentially erroneous – circuits, on the BQP-device, to decide each instance inP p. Call the outputs{S j} |Pp| j=1 and assumeS 0 is the BQP-device’s solution top

  2. [10]

    ACKNOWLEDGEMENTS The author acknowledges the support of the Quantum Ad- vantage Pathfinder (EP/X026167/1)

    Initialize a variable,overall confidence=1 5.ForS j in{S j} |Pp| j=1: (a)If(S j ,S ′ j ): i.overall confidence*=(1−C j) RETURN: S 0 (the result the BQP-device gives forp) and overall confidence IV . ACKNOWLEDGEMENTS The author acknowledges the support of the Quantum Ad- vantag...

  3. [11]

    Arora and B

    S. Arora and B. Barak,Computational Complexity: A Modern Approach(Cambridge University Press, 2009) pp. 11–23

    2009

  4. [12]

    Dean, Computational Complexity Theory, inThe Stanford Encyclopedia of Philosophy, edited by E

    W. Dean, Computational Complexity Theory, inThe Stanford Encyclopedia of Philosophy, edited by E. N. Zalta (Metaphysics Research Lab, Stanford University, 2021) Fall 2021 ed

    2021

  5. [13]

    The National Quantum Computing Centre, What is quantum computing? (2025)

    2025

  6. [14]

    Bernstein and U

    E. Bernstein and U. Vazirani, Quantum Complexity Theory, SIAM J. Comput.26, 1411–1473 (1997)

    1997

  7. [15]

    Aaronson, BQP and the Polynomial Hierarchy (2009), arXiv:0910.4698 [quant-ph]

    S. Aaronson, BQP and the Polynomial Hierarchy (2009), arXiv:0910.4698 [quant-ph]

    2009 arXiv

  8. [16]

    Edmonds, Paths, trees, and flowers, Canadian Journal of Mathematics17, 449–467 (1965)

    J. Edmonds, Paths, trees, and flowers, Canadian Journal of Mathematics17, 449–467 (1965)

    1965

  9. [17]

    Cobham, The intrinsic computational difficulty of functions, inLogic, methodology and philosophy of science, edited by Y

    A. Cobham, The intrinsic computational difficulty of functions, inLogic, methodology and philosophy of science, edited by Y . Bar-Hillel (North-Holland Pub. Co., 1965) pp. 24–30

    1965

  10. [18]

    Sipser, Introduction to the theory of computation (Course Technology, Boston, MA, 1997) pp

    M. Sipser, Introduction to the theory of computation (Course Technology, Boston, MA, 1997) pp. 234 – 241, 1st ed

    1997

  11. [19]

    Sipser, Introduction to the theory of computation (Course Technology, Boston, MA, 1997) pp

    M. Sipser, Introduction to the theory of computation (Course Technology, Boston, MA, 1997) pp. 241 – 247, 1st ed

    1997

  12. [20]

    Sipser, Introduction to the theory of computation (Course Technology, Boston, MA, 1997) pp

    M. Sipser, Introduction to the theory of computation (Course Technology, Boston, MA, 1997) pp. 138 – 140, 1st ed

    1997

  13. [21]

    Dempsey and C

    R. Dempsey and C. Guinn, A Phase Transition in Minesweeper, in10th International Conference on Fun with Algorithms (FUN 2021), Leibniz International Proceedings in Informatics (LIPIcs), V ol. 157, edited by M. Farach-Colton, G. Prencipe, and R. Uehara (Schloss Dagstuhl – Leibn...

    2021

  14. [22]

    Achlioptas and E

    D. Achlioptas and E. Friedgut, A sharp threshold for k- colorability, Random Structures & Algorithms14, 63 (1999)

    1999

  15. [23]

    I. P. Gent and T. Walsh, The sat phase transition, inProceed- ings of the 11th European Conference on Artificial Intelligence, ECAI’94 (John Wiley & Sons, Inc., USA, 1994) p. 105–109

    1994

  16. [24]

    D. L. Stein and C. M. Newman,Spin glasses and complexity (Princeton University Press, 2013)

    2013

  17. [25]

    Galam, Y

    S. Galam, Y . Gefen(Feigenblat), and Y . Shapir, Sociophysics: A new approach of sociological collective behaviour. i. mean- behaviour description of a strike, The Journal of Mathematical Sociology9, 1 (1982)

    1982

  18. [26]

    Jackson, Explaining the ubiquity of phase transitions in de- cision problems (2025), arXiv:2501.14569 [cs.CC]

    A. Jackson, Explaining the ubiquity of phase transitions in de- cision problems (2025), arXiv:2501.14569 [cs.CC]

    2025 arXiv

  19. [27]

    Schawe, R

    H. Schawe, R. Bleim, and A. K. Hartmann, Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming, PLOS ONE14, 1 (2019)

    2019

  20. [28]

    J. M. Crawford and L. D. Auton, Experimental results on the crossover point in random 3-sat, Artificial Intelligence81, 31 (1996), frontiers in Problem Solving: Phase Transitions and Complexity

    1996

  21. [29]

    D. D. Bailey, V . Dalmau, and P. G. Kolaitis, Phase transitions of PP-complete satisfiability problems, Discrete Applied Math- ematics155, 1627 (2007), SAT 2001, the Fourth International Symposium on the Theory and Applications of Satisfiability Testing

    2007

  22. [30]

    Hook and H

    J. Hook and H. Hall, Solid state physics (Wiley, 1991) pp. 219– 251, 2nd ed. 6

    1991

  23. [31]

    K. H. J. Buschow and F. R. de Boer, The magnetically or- dered state, inPhysics of Magnetism and Magnetic Materials (Springer US, Boston, MA, 2003) pp. 19–42

    2003

  24. [32]

    Hook and H

    J. Hook and H. Hall, Solid state physics (Wiley, 1991) pp. 1–32, 2nd ed

    1991

  25. [33]

    Hook and H

    J. Hook and H. Hall, Solid state physics (Wiley, 1991) pp. 278– 314, 2nd ed

    1991

  26. [34]

    Or at least does beyond a short distance from the threshold value

  27. [35]

    In fact, throughout this paper I will regularly use this function and define it polymorphically to return the length of a word regardless of the alphabet the word is formed from

  28. [36]

    Farag ´o and R

    A. Farag ´o and R. Xu, A new algorithm design technique for hard problems (2020)

    2020

  29. [37]

    Cai, Cs 810: Introduction to complexity theory

    J.-Y . Cai, Cs 810: Introduction to complexity theory. lecture 11: P=poly, sparse sets, and mahaney’s theorem. (2003)

    2003

  30. [38]

    The complexity class corresponding to practical quantum com- puting [42]

  31. [39]

    Jackson, Extensively not p-bi-immune promisebqp- complete languages (2024), arXiv:2406.16764 [cs.CC]

    A. Jackson, Extensively not p-bi-immune promisebqp- complete languages (2024), arXiv:2406.16764 [cs.CC]

    2024 arXiv

  32. [40]

    S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, Experi- mental verification of quantum computation, Nature Physics9, 727 (2013)

    2013

  33. [41]

    McKague, Interactive proofs forBQPvia self-tested graph states, Theory of Computing12, 1 (2016)

    M. McKague, Interactive proofs forBQPvia self-tested graph states, Theory of Computing12, 1 (2016)

    2016

  34. [42]

    Hangleiter, M

    D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert, Direct certification of a class of quantum simulations, Quantum Sci- ence and Technology2, 015004 (2017)

    2017

  35. [43]

    Kashefi and P

    E. Kashefi and P. Wallden, Optimised resource construction for verifiable quantum computation, Journal of Physics A: Mathe- matical and Theoretical50, 145306 (2017)

    2017

  36. [44]

    Gheorghiu, T

    A. Gheorghiu, T. Kapourniotis, and E. Kashefi, Verification of quantum computation: An overview of existing approaches, Theory of Computing Systems63, 715–808 (2018)

    2018

  37. [45]

    Ferracin, T

    S. Ferracin, T. Kapourniotis, and A. Datta, Accrediting outputs of noisy intermediate-scale quantum computing devices, New Journal of Physics21, 113038 (2019)

    2019

  38. [46]

    Markham and A

    D. Markham and A. Krause, A simple protocol for certifying graph states and applications in quantum networks, Cryptogra- phy4, 3 (2020)

    2020

  39. [47]

    Ferracin, S

    S. Ferracin, S. T. Merkel, D. McKay, and A. Datta, Experimen- tal accreditation of outputs of noisy quantum computers, Phys- ical Review A104, 10.1103/physreva.104.042603 (2021)

    2021 doi

  40. [48]

    Jackson, Accreditation against limited adversarial noise (2025), arXiv:2409.03995 [quant-ph]

    A. Jackson, Accreditation against limited adversarial noise (2025), arXiv:2409.03995 [quant-ph]

    2025

  41. [49]

    Shaffer, E

    R. Shaffer, E. Megidish, J. Broz, W.-T. Chen, and H. H ¨affner, Practical verification protocols for analog quantum simulators, npj Quantum Information7, 46 (2021)

    2021

  42. [50]

    Jackson, T

    A. Jackson, T. Kapourniotis, and A. Datta, Accreditation of analogue quantum simulators, Proceedings of the National Academy of Sciences121, e2309627121 (2024)

    2024

  43. [51]

    Jackson and A

    A. Jackson and A. Datta, Improved accreditation of ana- logue quantum simulation and establishing quantum advantage (2025), arXiv:2502.06463 [quant-ph]

    2025 arXiv

  44. [52]

    Arora and B

    S. Arora and B. Barak,Computational Complexity: A Modern Approach(Cambridge University Press, 2009)

    2009

  45. [53]

    · j is also defined polymorphically to function correctly re- gardless of the alphabet in use

  46. [54]

    B3, is zero-indexing

    Note that this formula, in Eqn. B3, is zero-indexing

  47. [55]

    I note that|α Π(n)|can always be efficiently calculated without using Eqn. B3

  48. [56]

    I note thatϕ −1 :Σ∗−→Σ∗ must exist and be a bijection asϕis due toξ,ξ −1, andξ−1◦ϕ◦ξbeing bijections

  49. [57]

    4 suffices as the key point is the symmetry of the relationship

    This can be shown more formally, but Fig. 4 suffices as the key point is the symmetry of the relationship

  50. [58]

    And hence so doesξ −1 :Π−→Σ ∗

  51. [59]

    I note that the summation over multipleB ϕ j is required because the set of words ofΠ∗ of a given length is larger than the set of words ofΣ∗ of the same length (as|Σ|<|Π|)

  52. [60]

    Also note that the argument above goes through if reversed

  53. [61]

    By which I mean there are not elements not in that set between elements of that set

  54. [62]

    As they are designed to encode exactly the same numbers be- fore and afterξorξ −1 act on them, soξandξ −1 preserve the ordering inherited from the encoding of the numbers

  55. [63]

    Antonopoulos, Computational complexity graduate course

    A. Antonopoulos, Computational complexity graduate course. 7 Appendix A: Alternative Expression of Being Not-Anywhere-Exponentially-Unbalanced Def. 15, the definition of being not-anywhere-exponentially-unbalanced used herein and in Ref. [16], may be re-expressed as an equival...

  56. [64]

    additional property

    Proving Lemma 3 Lemma 2.Any language over an alphabetΣ ={1,2,...,|Σ|}is preserving-P-isomorphic to a language over the alphabetΠ = {1,2,...,|Σ|,|Σ|+1}. Proof.LetL⊆Σ ∗ be a language. I then aim to construct the required language overΠthatLis preserving-P-isomorphic to. This is ...

  57. [65]

    does not return⊥ for)

    Proving Lemma 6 Lemma 4.Ifξ,ϕ,L, andHare as in the proof of Lemma 3,∀n∈N 0, there existsχ low(n),χ upp (n)∈N 0 such that: Bξ−1◦ϕ◦ξ n ∩H∩Ξ H = χupp (n)X j=χlow(n) α j Bϕ j∩L∩Ξ L ,(B28) where α j∈R + χupp (n) j=χlow(n) satisfies Pχupp (n) j=χlow(n) α j Bϕ j = Bξ−1◦ϕ◦ξ n withα j ...

  58. [66]

    the elements ofB ϕ n afterϕacts on them are contiguous [51] – according to the ordering that follows fromθ Σ – and are sandwiched between the elements ofB ϕ n−1 (on one side) andB ϕ n+1 (on the other)

  59. [67]

    B33, lete 0∈B ϕ

    the elements ofB ξ−1◦ϕ◦ξ n afterξ−1◦ϕ◦ξacts on them are also contiguous, this time according to the ordering that follows fromθ Π; 3.ξandξ −1 preserve the orderings ofΣ∗ according toθ Σ and the orderings ofΠ∗ according toθ Π, respectively [52]; there existsχ low(n),χ upp (n)∈N...

  60. [68]

    filling up

    This is equivalent, givene 0∈Σ∗, to there not existing ay 0∈Σ∗ such that: θΣ ϕy0 =θ Σ ϕe0 −1.(B34) By diagram chasing on Fig. 5, Eqn. B34 can be seen to be equivalent to there not existing ay 0∈Σ∗ such that: θΠ ξϕy0 =θ Π ξϕe0 −1.(B35) Such ay 0∈Σ∗ satisfying Eqn. B35 would be ...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.