Support geometry impacts complexity of LABS combinatorial problems
On the Support Geometry and Complexity of LABS
Computational Complexity
Summary
Certain complex problems called LABS appear in designing sequences and physics, but their difficulty is not fully understood. The authors studied how changing the shape of allowed positions (support geometry) affects the problem's complexity. They found that when constraints are simple, the problem can be solved quickly, but when they become slightly more complex, it becomes very hard to decide. Their work clarifies when these problems are easy or hard based on the structure of allowed terms.
What this means in practice
- •For sequence designers: Determine when particular sequence design problems can be solved efficiently or are computationally difficult based on support geometry constraints.
- •For statistical physics modelers: Identify classes of zero-energy feasibility problems that are tractable or intractable depending on geometrical restrictions within physical models.
A theory result. No direct application yet.
Authors
William Cruz-Santos
Abstract
LABS are a fundamental combinatorial optimization problem arising in sequence design and statistical physics, yet the formal complexity of the standard fixed-geometry problem remains unresolved. We study how zero-energy complexity changes when support geometry is included as part of the input and then progressively restricted. For unary standard LABS, we establish membership in $\NP$ and a sparsity/Mahaney consequence: Karp NP-hardness would imply $\Ptime=\NP$. For Pair-Set-LABS and Masked-LABS, zero-energy feasibility is polynomial-time decidable when every pair group or masked row has at most three terms and is NP-complete when four terms are allowed. NP-completeness persists when active supports are restricted to contiguous intervals.