Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.02622 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |