pith. sign in

arxiv: 2604.05661 · v1 · submitted 2026-04-07 · 💻 cs.DS · cs.DM· math.CO

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics

Afrouz Jabal Ameli , Jesper Nederlof , Shengzhe Wang This is my paper

Pith reviewed 2026-05-10 18:57 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO
keywords space-time tradeoffsTraveling Salesperson Problemchain efficiencyset systemspermutation problemsextremal combinatoricssemi-rings
0
0 comments X

The pith

An algorithm solves N-vertex TSP instances with space S and time T where S times T is at most 3.7493 to the power N.

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

The paper develops improved space-time tradeoffs for permutation problems such as the Traveling Salesperson Problem by defining a new parameter called chain efficiency for set systems. High chain efficiency in these systems translates directly into algorithms whose combined space and time requirements grow more slowly than before. A sympathetic reader would care because the new bound breaks through a barrier that earlier work had shown to be optimal within its framework, opening the door to more practical exact solutions for hard combinatorial problems under memory limits.

Core claim

The authors define chain efficiency of a set system as the number of its maximal chains divided by the cardinality of the system. They give explicit constructions of set systems with high chain efficiency that, via a reduction to permutation problems over additively idempotent semi-rings, yield an algorithm for the Traveling Salesperson Problem satisfying S·T ≤ 3.7493^N. This improves the prior bound of 3.9271^N and disproves a conjecture of Johnson, Leader and Russel on the maximum achievable efficiency.

What carries the argument

Chain efficiency of a set system, which counts maximal chains relative to system size and drives the reduction to space-time efficient algorithms for permutation problems.

If this is right

  • The same tradeoffs apply to other permutation problems such as Hamiltonian path and cycle.
  • Explicit constructions of set systems achieve higher chain efficiency than previously conjectured to be possible.
  • The results hold for general additively idempotent semi-rings, not just special cases like the boolean semiring.

Where Pith is reading between the lines

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

  • The combinatorial technique could be reused to tighten space-time bounds for other NP-hard problems that admit subset or chain representations.
  • Further improvements in set system constructions would directly lower the base in the tradeoff.
  • Extremal combinatorics may supply similar parameters for designing resource-bounded exact algorithms in additional domains.

Load-bearing premise

The explicit set system constructions reach the chain efficiency levels needed for the 3.7493 base, and the reduction from these systems to the algorithms for permutation problems incurs no significant loss in the bound.

What would settle it

A proof that no set system can achieve chain efficiency high enough to support a base of 3.7493 or lower, or a concrete TSP instance on small N where the algorithm's observed space-time product exceeds the claimed bound.

read the original abstract

We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem that solves $N$-vertex instances using space $S$ and time $T$ where $S\cdot T \leq 3.7493^{N}$. This improves a previous work by Koivisto and Parviainen [SODA'10] where $S\cdot T \leq 3.9271^N$, and overcomes a barrier they identified, as their bound was shown to be optimal within their framework. To get our results, we introduce a new parameter of a set system that we call the chain efficiency. This relates the number of maximal chains contained in the set system with the cardinality of the system. We show that set systems of high efficiency imply efficient space-time tradeoffs for permutation problems, and give constructions of set systems with high chain efficiency, disproving a conjecture by Johnson, Leader and Russel [Comb. Probab. Comput.'15].

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

3 major / 2 minor

Summary. The manuscript claims improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, it gives an algorithm for the Traveling Salesperson Problem on N-vertex instances satisfying S · T ≤ 3.7493^N. This improves the 3.9271^N bound of Koivisto and Parviainen (SODA 2010) and overcomes a barrier they identified. The improvement is obtained by defining a new parameter called chain efficiency for set systems (relating the number of maximal chains to the system cardinality), proving that high-efficiency systems yield efficient tradeoffs via a general reduction, and supplying explicit constructions that achieve higher efficiency than the Johnson-Leader-Russell bound, thereby disproving their conjecture.

Significance. If the constructions and reduction are correct, the work is significant because it supplies explicit combinatorial constructions and a general reduction framework that convert extremal parameters into concrete algorithmic tradeoffs. The disproof of the Johnson-Leader-Russell conjecture and the numerical improvement over a previously optimal bound within its framework are clear strengths. The approach may extend to other permutation problems and highlights a fruitful connection between extremal combinatorics and dynamic programming.

major comments (3)
  1. [Section 4] Section 4 (chain-efficiency definition and Theorem 4.3): the claimed translation from the efficiency value of the new constructions to the precise base 3.7493 must be verified for exactness; an off-by-one error in counting maximal chains or a normalization issue in the efficiency formula would alter the exponent base.
  2. [Section 5] Section 5 (explicit constructions): the set-system constructions must be checked to confirm that their chain-efficiency values are achieved without hidden exponential losses when plugged into the reduction; the paper states they exceed the Johnson-Leader-Russell bound, but the precise numerical mapping to 3.7493 needs explicit verification.
  3. [Section 6] Section 6 (reduction to semi-ring permutation problems): the general reduction from high-efficiency set systems to the S·T tradeoff for TSP must be confirmed to incur no unstated polynomial or exponential overhead in the DP state space; any such factor would change the concrete constant.
minor comments (2)
  1. [Abstract] The abstract could briefly state the name of the conjecture being disproved for immediate context.
  2. [Section 2] Notation for additively idempotent semi-rings in the preliminaries could include a short example to aid readers unfamiliar with the setting.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their thorough review and positive evaluation of the significance of our results. We address each major comment below with clarifications on the calculations and constructions.

read point-by-point responses

  1. Referee: [Section 4] Section 4 (chain-efficiency definition and Theorem 4.3): the claimed translation from the efficiency value of the new constructions to the precise base 3.7493 must be verified for exactness; an off-by-one error in counting maximal chains or a normalization issue in the efficiency formula would alter the exponent base.

    Authors: We have re-verified the derivations in Section 4 and Theorem 4.3. The chain efficiency parameter is defined to relate |F| and the number of maximal chains exactly, and the tradeoff base is obtained by direct substitution into the formula without off-by-one errors or normalization discrepancies. The counting follows the set-system definition precisely. We will add an explicit numerical walkthrough of the base computation in the revision for easier verification. revision: partial

  2. Referee: [Section 5] Section 5 (explicit constructions): the set-system constructions must be checked to confirm that their chain-efficiency values are achieved without hidden exponential losses when plugged into the reduction; the paper states they exceed the Johnson-Leader-Russell bound, but the precise numerical mapping to 3.7493 needs explicit verification.

    Authors: The constructions in Section 5 are fully explicit, and the chain-efficiency values are computed directly from the system cardinality and maximal-chain count with no hidden exponential losses. Substituting these values into the reduction yields the exact base 3.7493, which exceeds the Johnson-Leader-Russell bound and disproves the conjecture. We will include the intermediate efficiency numbers and the mapping steps in the revised manuscript. revision: partial

  3. Referee: [Section 6] Section 6 (reduction to semi-ring permutation problems): the general reduction from high-efficiency set systems to the S·T tradeoff for TSP must be confirmed to incur no unstated polynomial or exponential overhead in the DP state space; any such factor would change the concrete constant.

    Authors: The reduction in Section 6 uses dynamic programming whose state space size equals the set-system cardinality and whose time is proportional to the number of maximal chains (with only polynomial-in-N factors). These polynomial factors do not affect the exponential base of the S·T product. The analysis contains no unstated exponential overheads, and the claimed bound S·T ≤ 3.7493^N follows directly for TSP over the semi-ring. revision: no

Circularity Check

0 steps flagged

No circularity; improvement driven by explicit new constructions

full rationale

The derivation introduces the independent parameter of chain efficiency for set systems, proves that high-efficiency systems yield space-time tradeoffs for permutation problems over additively idempotent semirings via a general reduction, and supplies explicit constructions achieving efficiency values that produce the concrete base 3.7493. None of these steps reduce to self-definition, fitted inputs renamed as predictions, or load-bearing self-citations; the numerical improvement is obtained from the combinatorial constructions themselves rather than from re-deriving the target bound. The paper is self-contained against external benchmarks (prior conjectures and algorithms) with no circular reduction visible.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the new definition of chain efficiency and on combinatorial constructions that achieve high values of this parameter; these are introduced in the paper rather than taken from prior literature.

axioms (1)
  • standard math Standard facts from extremal set theory relating maximal chains to the size of a set system.
    Invoked to bound the efficiency parameter and to connect it to dynamic-programming state compression.
invented entities (1)
  • chain efficiency no independent evidence
    purpose: A new quantitative measure of a set system that counts maximal chains relative to cardinality and is used to derive space-time tradeoffs.
    Defined and constructed in this paper to overcome the barrier identified by Koivisto and Parviainen.

pith-pipeline@v0.9.0 · 5492 in / 1390 out tokens · 60641 ms · 2026-05-10T18:57:11.642099+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

31 extracted references · 31 canonical work pages

  1. [1]

    Alon and P

    N. Alon and P. Frankl. The maximum number of disjoint pairs in a family of subsets.Graphs Comb., 1(1):13–21, 1985

    work page 1985

  2. [2]

    Austrin, P

    P. Austrin, P. Kaski, M. Koivisto, and J. Määttä. Space-time tradeoffs for Subset Sum: An improved worst case algorithm. In F. V. Fomin, R. Freivalds, M. Z. Kwiatkowska, and D. Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Lecture Notes in Computer Scie...

    work page 2013

  3. [3]

    Bansal, S

    N. Bansal, S. Garg, J. Nederlof, and N. Vyas. Faster space-efficient algorithms for Subset Sum, k-Sum, and related problems.SIAM J. Comput., 47(5):1755–1777, 2018

    work page 2018

  4. [4]

    R. Bellman. Dynamic programming treatment of the Travelling Salesman Problem.J. ACM, 9(1):61–63, 1962

    work page 1962

  5. [5]

    Belova, N

    T. Belova, N. Chukhin, A. S. Kulikov, and I. Mihajlin. Improved space bounds for Subset Sum. In T. M. Chan, J. Fischer, J. Iacono, and G. Herman, editors,32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024, LIPIcs, pages 21:1–21:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024

    work page 2024

  6. [6]

    Björklund

    A. Björklund. Determinant sums for undirected Hamiltonicity.SIAM J. Comput., 43(1):280–299, 2014

    work page 2014

  7. [7]

    G. R. Brightwell and P. Tetali. The number of linear extensions of the Boolean lattice.Order, 20(4):333–345, 2003

    work page 2003

  8. [8]

    J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S.-H. Sze, and F. Zhang. Random- ized Divide-and-Conquer: Improved path, matching, and packing algorithms.SIAM Journal on Computing, 38(6):2526–2547, 2009

    work page 2009

  9. [9]

    Dinur, O

    I. Dinur, O. Dunkelman, N. Keller, and A. Shamir. Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems. In R. Safavi- Naini and R. Canetti, editors,Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, Lectur...

    work page 2012

  10. [10]

    S. J. Dittmer and I. Pak. Counting linear extensions of restricted posets.Electron. J. Comb., 27(4):4, 2020

    work page 2020

  11. [11]

    F. V. Fomin and P. Kaski. Exact exponential algorithms.Commun. ACM, 56(3):80–88, 2013

    work page 2013

  12. [12]

    F. V. Fomin and D. Kratsch.Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010

    work page 2010

  13. [13]

    Frankl and Z

    P. Frankl and Z. Füredi. A short proof for a theorem of Harper about Hamming-spheres.Discrete Mathematics, 34:311–313, 1981

    work page 1981

  14. [14]

    Gurevich and S

    Y. Gurevich and S. Shelah. Expected computation time for Hamiltonian path problem.SIAM J. Comput., 16(3):486–502, 1987. 17

    work page 1987

  15. [15]

    L. H. Harper. Optimal numberings and isoperimetric problems on graphs.Journal of Combinatorial Theory, 1:385–393, 1966

    work page 1966

  16. [16]

    Held and R

    M. Held and R. M. Karp. A dynamic programming approach to sequencing problems. In T. C. Rowan, editor,Proceedings of the 16th ACM national meeting, ACM 1961, USA, page 71. ACM, 1961

    work page 1961

  17. [17]

    Horowitz and S

    E. Horowitz and S. Sahni. Computing partitions with applications to the Knapsack problem.J. ACM, 21(2):277–292, 1974

    work page 1974

  18. [18]

    Hunter, A

    Z. Hunter, A. Milojević, B. Sudakov, and I. Tomon. Disjoint pairs in set systems and combinatorics of low rank matrices.arXiv preprint arXiv:2411.13510, 2024

    work page arXiv 2024

  19. [19]

    D. S. Johnson. Approximation algorithms for combinatorial problems. In A. V. Aho, A. Borodin, R. L. Constable, R. W. Floyd, M. A. Harrison, R. M. Karp, and H. R. Strong, editors,Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA, pages 38–49. ACM, 1973

    work page 1973

  20. [20]

    J. R. Johnson, I. Leader, and P. A. Russell. Set systems containing many maximal chains.Comb. Probab. Comput., 24(3):480–485, 2015

    work page 2015

  21. [21]

    Kahn and J

    J. Kahn and J. H. Kim. Entropy and sorting. InProceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 178–187, 1992

    work page 1992

  22. [22]

    Kangas, T

    K. Kangas, T. Hankala, T. M. Niinimäki, and M. Koivisto. Counting linear extensions of sparse posets. In S. Kambhampati, editor,Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 603–609. IJCAI/AAAI Press, 2016

    work page 2016

  23. [23]

    R. M. Karp. Dynamic programming meets the principle of inclusion and exclusion.Oper. Res. Lett., 1(2):49–51, 1982

    work page 1982

  24. [24]

    Koivisto and P

    M. Koivisto and P. Parviainen. A space-time tradeoff for permutation problems. In M. Charikar, editor,Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 484–492. SIAM, 2010

    work page 2010

  25. [25]

    Nederlof

    J. Nederlof. Bipartite TSP inO(1.9999 n)time, assuming quadratic time matrix multiplication. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, editors,Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 40–53. ACM, 2020

    work page 2020

  26. [26]

    fine-grained complexity of NP -complete problems

    J. Nederlof. An invitation to "fine-grained complexity of NP -complete problems".Comput. Sci. Rev., 61:100919, 2026

    work page 2026

  27. [27]

    Nederlof and K

    J. Nederlof and K. Wegrzycki. Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors. In S. Khuller and V. V. Williams, editors,STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1670–1683. ACM, 2021

    work page 2021

  28. [28]

    Schroeppel and A

    R. Schroeppel and A. Shamir. AT=O(2 n/2),S=O(2 n/4)algorithm for certain NP-complete problems.SIAM J. Comput., 10(3):456–464, 1981. 18

    work page 1981

  29. [29]

    Talvitie and M

    T. Talvitie and M. Koivisto. Approximate counting of linear extensions in practice.J. Artif. Intell. Res., 81:643–681, 2024

    work page 2024

  30. [30]

    G. J. Woeginger. Space and time complexity of exact algorithms: Some open problems (invited talk). In R. G. Downey, M. R. Fellows, and F. K. H. A. Dehne, editors,Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings, Lecture Notes in Computer Science, pages 281–290. Springer, 2004

    work page 2004

  31. [31]

    G. J. Woeginger. Open problems around exact algorithms.Discret. Appl. Math., 156(3):397–405, 2008. ATSPinO ∗(4N )time and polynomial space The algorithm is a (small) adjustment of the4N N O(logn) time algorithm of [14] (see also e.g. [12, Section 10.1] and seems to be folklore. The adjustment that avoids theN O(logN) term in the running time is to simulta...

    work page 2008