Pith. sign in

REVIEW 1 major objections 29 references

Minimization Principle for Polynomial-Time Predicates and Forcing in Bounded Arithmetic

T0 review · 1 major / 0 minor · reviewed 2026-06-28 · grok-4.3

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

Pith's one-line read A factorization hypothesis for oracle polynomial-time linear orders enables an approach to a nonstandard model that satisfies minimization for polynomial-time predicates but violates the tournament principle for polynomial-time graphs.

desk verdict This paper sketches a conditional separation in bounded arithmetic assuming an unproven factorization hypothesis, with the construction details left at a high level. read the letter →

arxiv 2606.01163 v1 pith:SPAUZD3T submitted 2026-05-31 math.LO

Mykyta Narusevych This is my paper · ORCID
classification math.LO
keywords boundedarithmeticminimizationschemetournamentprinciplepolynomial-timepredicatesnonstandardmodelsforcingfactorizationhypothesisoraclemachines
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

The paper introduces a factorization hypothesis applying to linear orders that oracle polynomial-time machines can define. Under the assumption that this hypothesis holds, it outlines a method for building a nonstandard model of arithmetic. In this model the minimization scheme holds when restricted to polynomial-time predicates, yet the tournament principle fails when the edge relation of the graph is also polynomial-time definable. A sympathetic reader cares because these two schemes are candidate axioms in bounded arithmetic, and showing they can be separated clarifies their relative strengths without relying on full consistency strength.

What carries the argument

The factorization hypothesis for linear orders definable by oracle polynomial-time machines, which supports the forcing construction of the separating nonstandard model.

What would settle it

An explicit linear order definable by an oracle polynomial-time machine that cannot be factored in the manner required by the hypothesis, or a direct proof that no nonstandard model can satisfy minimization for all polynomial-time predicates while violating the tournament principle for polynomial-time graphs.

Watch

Extended reading notes

Core claim

Assuming the factorization hypothesis for linear orders definable by oracle polynomial-time machines, there is an approach to constructing a nonstandard model satisfying the minimization scheme for polynomial-time predicates while violating the tournament principle for graphs with polynomial-time edge relation.

Load-bearing premise

The factorization hypothesis for linear orders definable by oracle polynomial-time machines holds.

Editorial extensions

If this is right

  • The constructed model obeys the minimization scheme whenever the predicate is polynomial-time.
  • The same model fails the tournament principle for any graph whose edge relation is polynomial-time.
  • The two schemes are thereby separated inside the language of bounded arithmetic under the stated hypothesis.
  • The separation is obtained by a forcing-style construction that preserves the polynomial-time definability constraints.

Reading between the lines

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

  • If the hypothesis is verified in standard models, the separation result would immediately transfer to questions about the relative strength of minimization and tournament axioms.
  • The same technique might extend to other combinatorial principles whose definability is limited to polynomial time.
  • Computational checks of the factorization property on small finite linear orders could provide evidence for or against the hypothesis.
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, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 0 minor

Summary. The paper formulates a factorization hypothesis for linear orders definable by oracle polynomial-time machines. Assuming this hypothesis, it provides an approach to constructing a nonstandard model satisfying the minimization scheme for polynomial-time predicates while violating the tournament principle for graphs with polynomial-time edge relation.

Significance. If the hypothesis is independently plausible and the sketched construction can be completed without circularity, the result would separate the minimization principle from the tournament principle inside a model of bounded arithmetic with polynomial-time definable sets and relations. This would be a contribution to the study of weak arithmetical theories and their connections to complexity, particularly if the forcing technique is made explicit.

major comments (1)
  1. [Abstract] Abstract: the central claim is an 'approach' conditional on the factorization hypothesis for linear orders definable by oracle P-time machines, yet no motivation, independent evidence, or outline of the model construction is supplied; without these the manuscript does not demonstrate that the math supports the stated separation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the review and the recommendation of major revision. We respond to the single major comment below, agreeing that the abstract requires expansion while defending the conditional nature of the result.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim is an 'approach' conditional on the factorization hypothesis for linear orders definable by oracle P-time machines, yet no motivation, independent evidence, or outline of the model construction is supplied; without these the manuscript does not demonstrate that the math supports the stated separation.

    Authors: The manuscript is a concise announcement introducing the factorization hypothesis and outlining a conditional construction. We agree the abstract is too terse and does not sufficiently motivate the hypothesis or sketch the model construction. In revision we will expand the abstract to include (i) motivation drawn from the study of P-minimization versus tournament principles in bounded arithmetic and (ii) a high-level outline of the forcing construction that avoids circularity by separating the hypothesis from the model-building steps. The body already contains the technical formulation; we will make the sketch more explicit. Independent evidence for the hypothesis itself is not supplied because it is a new conjecture; we will add a paragraph discussing its plausibility relative to known factorization properties of P-time orders, but verification remains open. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper formulates a factorization hypothesis and states all results as conditional on assuming it, providing an approach to a model construction under that assumption. No equations, derivations, or self-citations are quoted that reduce the claimed construction to the hypothesis by construction or force the outcome via fitted inputs or renamed results. The argument is self-contained as an explicit conditional statement with no load-bearing steps that match the enumerated circularity patterns.

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

The central claim rests entirely on the unproven factorization hypothesis introduced in the abstract; no free parameters, invented entities, or additional axioms are mentioned.

assumptions (1)
  • ad hoc to paper Factorization hypothesis for linear orders definable by oracle polynomial-time machines
    This is the explicit assumption required for the model construction described in the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimization Principle for Polynomial-Time Predicates and Forcing in Bounded Arithmetic." pith.science (2026). https://pith.science/paper/SPAUZD3T

@misc{pith2026260601163,
  author       = {Pith},
  title        = {Pith review of: Minimization Principle for Polynomial-Time Predicates and Forcing in Bounded Arithmetic},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SPAUZD3T}},
  note         = {Machine review of arXiv:2606.01163}
}
read the original abstract

We formulate a factorization hypothesis for linear orders definable by oracle polynomial-time machines. Assuming this hypothesis, we provide an approach to constructing a nonstandard model satisfying the minimization scheme for polynomial-time predicates while violating the tournament principle for graphs with polynomial-time edge relation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 6 canonical work pages

  1. [1]

    Context and the

    Kaye, R. , title =. 1991 , abstract =. doi:10.1093/oso/9780198532132.001.0001 , url =

    work page doi:10.1093/oso/9780198532132.001.0001 1991

  2. [2]

    Buss,. Bounded. 1985 , school =

    1985

  3. [3]

    2024 , eprint=

    Models of Bounded Arithmetic and variants of Pigeonhole Principle , author=. 2024 , eprint=

    2024

  4. [4]

    2025 , eprint=

    An independence of the MIN principle from the PHP principle , author=. 2025 , eprint=

    2025

  5. [5]

    1963 , journal =

    The Independence of the Continuum Hypothesis , author =. 1963 , journal =

    1963

  6. [6]

    1988 , journal =

    Provability of the pigeonhole principle and the existence of infinitely many primes , author =. 1988 , journal =

    1988

  7. [7]

    1987 , school =

    Computational limitations of small depth circuits , author =. 1987 , school =

    1987

  8. [8]

    Proceedings of the IEEE 29th Annual Symposium on Foundations of Computer Science , year =

    The complexity of the pigeonhole principle , author =. Proceedings of the IEEE 29th Annual Symposium on Foundations of Computer Science , year =

Show all 29 references
  1. [9]

    1995 , journal =

    Exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle , author =. 1995 , journal =

    1995

  2. [10]

    and Skelley, A

    Krajíček, J. and Skelley, A. and Thapen, N. , journal =. N

  3. [11]

    and Krajíček, J

    Chiari, M. and Krajíček, J. , doi =. Witnessing. Journal of Symbolic Logic , number =

  4. [12]

    1993 , journal =

    Exponential lower bounds for the pigeonhole principle , author =. 1993 , journal =

    1993

  5. [13]

    Feasible mathematics , publisher =

    Parity and the. Feasible mathematics , publisher =. 1990 , author =

    1990

  6. [14]

    and Wilkie, A

    Paris, J. and Wilkie, A. Counting problems in bounded arithmetic. Methods in Mathematical Logic. 1985

    1985

  7. [15]

    Krajíček, J. , year=. Bounded Arithmetic, Propositional Logic and Complexity Theory , publisher=

  8. [16]

    2019 , publisher=

    Proof Complexity , author=. 2019 , publisher=

    2019

  9. [17]

    A simple proof of the

    Katona,. A simple proof of the. Journal of Combinatorial Theory, Series B , year =

  10. [18]

    and Krajíček, J

    Impagliazzo, R. and Krajíček, J. , number =. Mathematical Logic Quarterly , year =. doi:10.1002/1521-3870(200204)48:3 , title =

    doi

  11. [19]

    Arithmetic, proof theory and computational complexity , pages=

    Making infinite structures finite in models of second order bounded arithmetic , author=. Arithmetic, proof theory and computational complexity , pages=

  12. [20]

    , title =

    Müller, M. , title =. Annals of Pure and Applied Logic , year =

  13. [21]

    and Müller, M

    Atserias, A. and Müller, M. , title =. Archive for. 2015 , volume =

    2015

  14. [22]

    and Vishkin, U

    Megiddo, N. and Vishkin, U. , abstract =. On finding a minimum dominating set in a tournament , journal =. 1988 , issn =. doi:https://doi.org/10.1016/0304-3975(88)90131-4 , url =

    1988 doi

  15. [23]

    , title =

    Hanika, J. , title =. Mathematical Logic Quarterly , volume =. doi:https://doi.org/10.1002/malq.200410005 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/malq.200410005 , abstract =

    doi

  16. [24]

    On the complexity of the parity argument and other inefficient proofs of existence , journal =

    Papadimitriou,. On the complexity of the parity argument and other inefficient proofs of existence , journal =. 1994 , issn =. doi:https://doi.org/10.1016/S0022-0000(05)80063-7 , url =

    1994 doi

  17. [25]

    and Thapen, N

    Atserias, A. and Thapen, N. , title =. ACM Trans. Comput. Logic , month = nov, articleno =. 2014 , issue_date =. doi:10.1145/2629555 , abstract =

    2014 doi

  18. [26]

    Buss, S. R. and Kołodziejczyk, L. A. and Thapen, N. , journal =. FRAGMENTS OF APPROXIMATE COUNTING , urldate =

  19. [27]

    Journal of Symbolic Logic , number =

    Jeř. Journal of Symbolic Logic , number =. 2009 , doi =

    2009

  20. [28]

    and Ježil, O

    Honzik, R. and Ježil, O. and Narusevych, M. , title =

  21. [29]

    Krajíček, J. , year=. Forcing with Random Variables and Proof Complexity , publisher=

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.