PLS-completeness of string permutations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908454848823296 |
|---|---|
| author | Scheder, Dominik Tantow, Johannes |
| author_facet | Scheder, Dominik Tantow, Johannes |
| contents | Bitstrings can be permuted via permutations and compared via the lexicographic order. In this paper we study the complexity of finding a minimum of a bitstring via given permutations. As a global optima is known to be NP-complete, we study the local optima via the class PLS and show hardness for PLS. Additionally, we show that even for one permutation the global optimization is NP-complete and give a formula that has these permutation as symmetries. This answers an open question inspired from Kolodziejczyk and Thapen and stated at the SAT and interactions seminar in Dagstuhl. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02622 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | PLS-completeness of string permutations Scheder, Dominik Tantow, Johannes Computational Complexity Bitstrings can be permuted via permutations and compared via the lexicographic order. In this paper we study the complexity of finding a minimum of a bitstring via given permutations. As a global optima is known to be NP-complete, we study the local optima via the class PLS and show hardness for PLS. Additionally, we show that even for one permutation the global optimization is NP-complete and give a formula that has these permutation as symmetries. This answers an open question inspired from Kolodziejczyk and Thapen and stated at the SAT and interactions seminar in Dagstuhl. |
| title | PLS-completeness of string permutations |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2505.02622 |