Papers for

sequence designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Support geometry impacts complexity of LABS combinatorial problems

On the Support Geometry and Complexity of LABS

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.

Mon 19 OctComputational Complexity

The gist

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.

Open → 2610.27329v1