标题： 字符串排列的PLS完全性 显示英文标题

标题： PLS-completeness of string permutations

摘要： 通过排列可以对位串进行排列，并通过字典序进行比较。 在本文中，我们研究了通过给定排列找到位串最小值的复杂性。 由于全局最优已知为NP完全问题，我们通过PLS类研究局部最优，并证明了PLS的难度。 此外，我们证明即使对于一个排列，全局优化也是NP完全问题，并给出一个具有这些排列作为对称性的公式。 这回答了一个由Kolodziejczyk和Thapen提出的开放性问题，并在Dagstuhl的SAT和交互研讨会中提出。 显示英文摘要

摘要： 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.