On the Support Geometry and Complexity of LABS
Overview & Synopsis
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.
arxiv.org)
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | On the Support Geometry and Complexity of LABS |
|---|---|
| Author / Organization | William Cruz-Santos |
| Subject & Discipline | cs.CC |
| Categories | Science & Mathematics |
| Publication Year | 2026 |
| License / Rights | arXiv Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
arXiv
(arxiv.org)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-271481 |
| Original Source Link | Visit Source Page on arxiv.org » |