pith. sign in

arxiv: 2510.15712 · v3 · pith:2HIHHZ3Dnew · submitted 2025-10-17 · 💻 cs.CC · cs.DS

PLS-complete problems with lexicographic cost functions: Max-k-SAT and Abelian Permutation Orbit Minimization

Dominik Scheder , Johannes Tantow This is my paper

Pith reviewed 2026-05-21 20:42 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords PLS-completenesslexicographic costsMax-4-SATAbelian groupspermutation orbitslocal searchcongestion gamesNash equilibria
0
0 comments X

The pith

Finding a locally maximal assignment for 4-CNF with lexicographic clause weights is PLS-complete, and so is Abelian permutation orbit minimization even for cyclic groups or groups of involutions.

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

The paper establishes that local search remains PLS-complete for certain optimization problems even when costs are ordered lexicographically, with higher-indexed elements receiving exponentially higher priority. It proves that finding a locally maximal truth assignment in a 4-CNF formula under such weights is PLS-complete using single-variable flips, and extends the result to 3-CNF when pairs of variables may be flipped together. These hardness results are then applied to show that lexicographic local minimum orbit minimization stays PLS-complete for Abelian permutation groups, including the restricted cases where every group element has order two or the group is cyclic. The same techniques yield a streamlined proof that computing pure Nash equilibria in congestion games is PLS-complete for polynomial delay functions with positive coefficients, where the number of players per resource and strategies per player remain bounded.

Core claim

Finding a lexicographic local maximum for Max-4-SAT is PLS-complete, and the Abelian permutation orbit minimization problem remains PLS-complete even when every element of the group has order two or when the group is cyclic; these results also imply PLS-completeness for pure Nash equilibria in congestion games with exponential or polynomial delay functions having positive coefficients.

What carries the argument

Reductions from known PLS-complete problems that preserve both the strict lexicographic ordering of costs (via successive powers of two) and the exact correspondence between single or double flips and locally improving moves.

Load-bearing premise

The reductions preserve both the lexicographic ordering of costs and the exact correspondence between flips and local improvements.

What would settle it

A polynomial-time algorithm that finds a locally maximal assignment for every 4-CNF formula whose clauses receive lexicographic weights 2^i would falsify the PLS-completeness claim.

read the original abstract

How hard is it to find a local optimum? If we are given a graph and want to find a locally maximal cut--meaning that the number of edges in the cut can't be improved by moving a single vertex from one side to the other--then just iterating improving steps finds a local maximum in $ |E|$ steps. If, on the other hand, the edges are weighted, this problem becomes hard for the class PLS (Polynomial Local Search). We are interested in optimization problems with lexicographic costs. For Max-Cut this would mean that the edges $e_1,\dots, e_m$ have costs $c(e_i) = 2^i$. For such a cost function finding a global Max-Cut is easy. In contrast, we show that it is PLS-complete to find an assignment for a 4-CNF formula that is locally maximal (when the clauses have lexicographic weights); and also for a 3-CNF when we allow switching two variables at a time. We use these results to answer a question in Scheder and Tantow, who showed that finding a lexicographic local minimum of a string $s \in \{0,1\}^n$ under the action of a list of given permutations $\pi_1, \dots, \pi_k \in S_{n}$ is PLS-complete. They ask whether the problem stays PLS-complete when the $\pi_1,\dots,\pi_k$ commute, i.e., generate an Abelian subgroup $G$ of $S_n$. We show that it does, and in fact stays PLS-complete even (1) when every element in $G$ has order two or (2) when $G$ is cyclic. Additionally, we use it to further investigate the complexity of computing pure $\alpha$-Nash equilibria in congestion games. Using lexicographic 4-SAT, we obtain a simple proof of the PLS-completeness originally shown by Skopalik and V\"ocking that can be extended to exponential and polynomial delay functions with positive coefficients. The number of strategies per player and players per resource is bounded. However, the degree of the polynomials is not bounded by a constant.

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 proves PLS-completeness for finding locally maximal assignments in 4-CNF formulas under lexicographic clause weights, and for 3-CNF formulas under double-variable flips. It further shows that Abelian permutation orbit minimization remains PLS-complete even when the group is generated by involutions or is cyclic. These results yield a simplified proof of PLS-completeness for computing pure α-Nash equilibria in congestion games with polynomial delay functions of positive coefficients, where the number of strategies and players per resource is bounded.

Significance. If the reductions are correct, the results resolve an open question of Scheder and Tantow on Abelian groups, provide a streamlined proof for congestion-game equilibria, and illustrate how lexicographic costs can make global optimization trivial while keeping local search PLS-complete. The bounded-player/resource setting and extension to exponential/polynomial delays strengthen the applicability to game-theoretic local search.

major comments (2)
  1. [§3] §3 (reduction for lex-Max-4-SAT): the central claim that local maxima correspond exactly between source and target instances requires an explicit argument that gadget-clause weights (under the 2^i lex ordering) cannot be altered by a single flip in a way that changes a higher-order bit before any source clause is considered. The abstract and the preservation requirement noted in the reduction overview both flag this; without it, the PLS-membership and completeness correspondence is not secured.
  2. [§4] §4 (Abelian orbit minimization): the proofs that PLS-completeness holds for groups generated by order-two elements and for cyclic groups must verify that the chosen generators preserve the exact local-improvement correspondence under commuting permutations; any reuse of variables across main and auxiliary permutations risks breaking the local-optima bijection.
minor comments (2)
  1. [§5] The abstract states that the congestion-game result extends to exponential and polynomial delays with positive coefficients, but the precise statement of the delay-function class and the bound on polynomial degree should be clarified in the theorem statement.
  2. Ensure all citations to Scheder and Tantow and to Skopalik and Vöcking include full bibliographic details and page references for the open question and the original PLS-completeness result.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will incorporate explicit clarifications into the revised version.

read point-by-point responses

  1. Referee: [§3] §3 (reduction for lex-Max-4-SAT): the central claim that local maxima correspond exactly between source and target instances requires an explicit argument that gadget-clause weights (under the 2^i lex ordering) cannot be altered by a single flip in a way that changes a higher-order bit before any source clause is considered. The abstract and the preservation requirement noted in the reduction overview both flag this; without it, the PLS-membership and completeness correspondence is not secured.

    Authors: We agree that an explicit argument strengthens the proof. In the revision we will add a dedicated lemma in §3 showing that, under the 2^i lexicographic ordering, the gadget clauses are assigned strictly lower-significance bits than the source clauses. Consequently, any single variable flip that would alter a higher-order gadget bit must first produce an improving move on a source clause, contradicting local optimality in the target instance. This establishes the exact correspondence of local maxima and secures both PLS-membership and completeness. We will also cross-reference the lemma from the reduction overview. revision: yes

  2. Referee: [§4] §4 (Abelian orbit minimization): the proofs that PLS-completeness holds for groups generated by order-two elements and for cyclic groups must verify that the chosen generators preserve the exact local-improvement correspondence under commuting permutations; any reuse of variables across main and auxiliary permutations risks breaking the local-optima bijection.

    Authors: We will expand the proofs in §4 with an explicit verification subsection. Because the generators are chosen to produce an Abelian group, they commute by construction; we will state this and show that each generator induces an improving move in the orbit-minimization instance if and only if the corresponding move improves the source instance. In our construction the auxiliary permutations act on a disjoint set of fresh variables, so no reuse occurs and the local-optima bijection is preserved. We will add a short remark confirming the variable separation. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to prior open question; new reductions and proofs are independent

full rationale

This theoretical paper proves PLS-completeness for lexicographic Max-k-SAT and Abelian permutation orbit minimization via explicit reductions from established PLS-complete problems such as local Max-2-SAT or Circuit/Flip. The reductions are constructed to preserve the exact correspondence between single/double flips and local improvements under lexicographic ordering. Self-citation appears only to reference the authors' earlier work posing the Abelian question; the new proofs and gadget constructions stand independently and do not reduce to that citation by definition or construction. No fitted inputs, self-definitional elements, or load-bearing uniqueness theorems from overlapping authors are used. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard definition of the PLS class and on known PLS-complete problems from the literature; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (1)
  • standard math PLS contains local-search problems whose local improvement steps are polynomial-time verifiable.
    Used as the target class for the completeness proofs.

pith-pipeline@v0.9.0 · 5944 in / 1256 out tokens · 41781 ms · 2026-05-21T20:42:10.731534+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    On the Impact of Combinatorial Structure on Congestion Games

    Heiner Ackermann, Heiko R¨ oglin, and Berthold V¨ ocking. “On the Impact of Combinatorial Structure on Congestion Games”. In:47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, California, USA, October 21-24, 2006, Proceedings. IEEE Computer So- ciety, 2006, pp. 613–622.doi:10 . 1109 / FOCS . 2006 . 55.url:https : //doi.org...

    work page doi:10.1109/focs.2006.55 2006

  2. [2]

    Masset, R

    Christoph Buchheim and Michael J¨ unger. “Linear optimization over per- mutation groups”. In:Discret. Optim.2.4 (2005), pp. 308–319.doi:10. 1016/J.DISOPT.2005.08.005.url:https://doi.org/10.1016/j. disopt.2005.08.005

    work page doi:10.1016/j 2005

  3. [3]

    On approximate pure Nash equi- libria in weighted congestion games with polynomial latencies

    Ioannis Caragiannis and Angelo Fanelli. “On approximate pure Nash equi- libria in weighted congestion games with polynomial latencies”. In:J. Comput. Syst. Sci.117 (2021), pp. 40–48.doi:10.1016/J.JCSS.2020. 10.007.url:https://doi.org/10.1016/j.jcss.2020.10.007

    work page doi:10.1016/j.jcss.2020 2021

  4. [4]

    Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure

    Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopa- lik. “Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure”. In:ACM Trans. Eco- nomics and Comput.3.1 (2015), 2:1–2:32.doi:10.1145/2614687.url: https://doi.org/10.1145/2614687

    work page doi:10.1145/2614687.url: 2015

  5. [5]

    Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

    George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Po¸ cas, and Clara Waldmann. “Existence and Complexity of Approximate Equilibria in Weighted Congestion Games”. In:Math. Oper. Res.48.1 (2023), pp. 583–602.doi:10.1287/MOOR.2022.1272.url:https://doi. org/10.1287/moor.2022.1272

    work page doi:10.1287/moor.2022.1272.url:https://doi 2023

  6. [6]

    On thePLS-complexity of maximum constraint assignment

    Dominic Dumrauf and Burkhard Monien. “On thePLS-complexity of maximum constraint assignment”. In:Theor. Comput. Sci.469 (2013), pp. 24–52.doi:10.1016/J.TCS.2012.10.044.url:https://doi.org/ 10.1016/j.tcs.2012.10.044. 27

    work page doi:10.1016/j.tcs.2012.10.044.url:https://doi.org/ 2013

  7. [7]

    The com- plexity of pure Nash equilibria

    Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar. “The com- plexity of pure Nash equilibria”. In:Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16,

    work page

  8. [8]

    Papadimitriou, and Kunal Talwar

    Ed. by L´ aszl´ o Babai. ACM, 2004, pp. 604–612.doi:10 . 1145 / 1007352.1007445.url:https://doi.org/10.1145/1007352.1007445

    work page doi:10.1145/1007352.1007445 2004

  9. [9]

    Polynomial- Time Algorithms for Permutation Groups

    Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. “Polynomial- Time Algorithms for Permutation Groups”. In:21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980. IEEE Computer Society, 1980, pp. 36–41.doi:10.1109/ SFCS.1980.34.url:https://doi.org/10.1109/SFCS.1980.34

    work page doi:10.1109/sfcs.1980.34 1980

  10. [10]

    On the Smoothed Complexity of Combinatorial Local Search

    Yiannis Giannakopoulos, Alexander Grosz, and Themistoklis Melissour- gos. “On the Smoothed Complexity of Combinatorial Local Search”. In: 51st International Colloquium on Automata, Languages, and Program- ming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia. Ed. by Karl Bring- mann, Martin Grohe, Gabriele Puppis, and Ola Svensson. Vol. 297. LIPIcs. Schloss...

    work page doi:10.4230/lipics.icalp.2024.72.url:https://doi.org/10.4230/ 2024

  11. [11]

    Com- puting Approximate Equilibria in Weighted Congestion Games via Best- Responses

    Yiannis Giannakopoulos, Georgy Noarov, and Andreas S. Schulz. “Com- puting Approximate Equilibria in Weighted Congestion Games via Best- Responses”. In:Math. Oper. Res.47.1 (2022), pp. 643–664.doi:10.1287/ MOOR.2021.1144.url:https://doi.org/10.1287/moor.2021.1144

    work page doi:10.1287/moor.2021.1144 2022

  12. [12]

    The k-Opt Al- gorithm for the Traveling Salesman Problem Has Exponential Running Time for k≥5

    Sophia Heimann, Hung P. Hoang, and Stefan Hougardy. “The k-Opt Al- gorithm for the Traveling Salesman Problem Has Exponential Running Time for k≥5”. In:51st International Colloquium on Automata, Lan- guages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Esto- nia. Ed. by Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson. Vol. 297. L...

    work page doi:10.4230/lipics.icalp.2024.84 2024

  13. [13]

    How Easy is Local Search?

    David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. “How Easy is Local Search?” In:J. Comput. Syst. Sci.37.1 (1988), pp. 79– 100.doi:10.1016/0022-0000(88)90046-3.url:https://doi.org/10. 1016/0022-0000(88)90046-3

    work page doi:10.1016/0022-0000(88)90046-3.url:https://doi.org/10 1988

  14. [14]

    The Strength of the Dominance Rule

    Leszek Aleksander Kolodziejczyk and Neil Thapen. “The Strength of the Dominance Rule”. In:27th International Conference on Theory and Ap- plications of Satisfiability Testing, SAT 2024, August 21-24, 2024, Pune, India. Ed. by Supratik Chakraborty and Jie-Hong Roland Jiang. Vol. 305. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024, 20:1– ...

    work page doi:10.4230/lipics.sat.2024.20.url:https://doi.org/10 2024

  15. [15]

    On Finding Locally Optimal Solutions

    Mark W. Krentel. “On Finding Locally Optimal Solutions”. In:Proceed- ings: Fourth Annual Structure in Complexity Theory Conference, Univer- sity of Oregon, Eugene, Oregon, USA, June 19-22, 1989. IEEE Computer Society, 1989, pp. 132–137.doi:10.1109/SCT.1989.41819.url:https: //doi.org/10.1109/SCT.1989.41819

    work page doi:10.1109/sct.1989.41819.url:https: 1989

  16. [16]

    Structure in Locally Optimal Solutions (Extended Abstract)

    Mark W. Krentel. “Structure in Locally Optimal Solutions (Extended Abstract)”. In:30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989. IEEE Computer Society, 1989, pp. 216–221.doi:10 . 1109/SFCS.1989.63481.url:https://doi.org/10.1109/SFCS.1989. 63481

    work page doi:10.1109/sfcs.1989 1989

  17. [17]

    Efficient maximal cubic graph cuts (extended abstract)

    Martin Loebl. “Efficient Maximal Cubic Graph Cuts (Extended Abstract)”. In:Automata, Languages and Programming, 18th International Collo- quium, ICALP91, Madrid, Spain, July 8-12, 1991, Proceedings. Ed. by Javier Leach Albert, Burkhard Monien, and Mario Rodr´ ıguez-Artalejo. Vol. 510. Lecture Notes in Computer Science. Springer, 1991, pp. 351– 362.doi:10....

    work page doi:10.1007/3-540-54233-7 1991

  18. [18]

    The (generaliz ed) Post correspondence problem with lists consisting of two words is decidable

    Nimrod Megiddo and Christos H. Papadimitriou. “On Total Functions, Existence Theorems and Computational Complexity”. In:Theor. Comput. Sci.81.2 (1991), pp. 317–324.doi:10.1016/0304- 3975(91)90200- L. url:https://doi.org/10.1016/0304-3975(91)90200-L

    work page doi:10.1016/0304- 1991

  19. [19]

    On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

    Christos H. Papadimitriou. “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence”. In:J. Comput. Syst. Sci.48.3 (1994), pp. 498–532.doi:10 . 1016 / S0022 - 0000(05 ) 80063 - 7.url: https://doi.org/10.1016/S0022-0000(05)80063-7

    work page doi:10.1016/s0022-0000(05)80063-7 1994

  20. [20]

    Integer linear programs and local search for max-cut

    Svatopluk Poljak. “Integer Linear Programs and Local Search for Max- Cut”. In:SIAM J. Comput.24.4 (1995), pp. 822–839.doi:10 . 1137 / S0097539793245350.url:https://doi.org/10.1137/S0097539793245350

    work page doi:10.1137/s0097539793245350 1995

  21. [21]

    Simple Local Search Prob- lems That are Hard to Solve

    Alejandro A. Sch¨ affer and Mihalis Yannakakis. “Simple Local Search Prob- lems That are Hard to Solve”. In:SIAM J. Comput.20.1 (1991), pp. 56– 87.doi:10.1137/0220004.url:https://doi.org/10.1137/0220004

    work page doi:10.1137/0220004.url:https://doi.org/10.1137/0220004 1991

  22. [22]

    In 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

    Dominik Scheder and Johannes Tantow. “PLS-Completeness of String Permutations”. In:33rd Annual European Symposium on Algorithms, ESA 2025, September 15-17, 2025, Warsaw, Poland. Ed. by Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman. Vol. 351. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2025, 56:1–56:14.doi:10 . 4230/LIPICS....

    work page doi:10.4230/lipics 2025

  23. [23]

    Inapproximability of pure nash equilibria

    Alexander Skopalik and Berthold V¨ ocking. “Inapproximability of pure nash equilibria”. In:Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20,

    work page

  24. [24]

    [BPR15] Nir Bitansky, Omer Paneth, and Alon Rosen

    Ed. by Cynthia Dwork. ACM, 2008, pp. 355–364.doi:10.1145/ 1374376.1374428.url:https://doi.org/10.1145/1374376.1374428. 29

    work page doi:10.1145/1374376.1374428 2008