PLS-completeness of string permutations

DOI10.4230/LIPICS.ESA.2025.56MaRDI QIDQ7322457zbMATH OpenFDO

Authors D. Scheder, Johannes Tantow

Publication date 31 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2025.56

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• DRAT-trim: Efficient Checking and Trimming Using Expressive Clausal Proofs
• Expressing symmetry breaking in DRAT proofs
• How easy is local search?
• Linear optimization over permutation groups
• On the \(\mathcal {PLS}\)-complexity of maximum constraint assignment
• Simple Local Search Problems that are Hard to Solve
• The complexity of gradient descent: CLS = PPAD ∩ PLS
• The complexity of pure Nash equilibria
• The strength of the dominance rule

This page was built for publication: PLS-completeness of string permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322457)