Metraipolis › archive › dc_6af290ca0381
Quadratic Word Equations with a Linear Side: Polynomial Nielsen Graph Diameter and NP-Completeness — arXiv:2609.21785
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.21785
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T02:51:55.155Z
- SHA-256 of the archived text
7546c4c32f0c9e78a7dfb7825b1b3c3ff1727c60d2f0621602e561e488ee62d6- Stable URL of this page
https://metraipolis.com/documento/dc_6af290ca0381
How to cite
Quadratic Word Equations with a Linear Side: Polynomial Nielsen Graph Diameter and NP-Completeness — arXiv:2609.21785 — arXiv (en), https://arxiv.org/abs/2609.21785 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6af290ca0381 (Metraipolis archive dc_6af290ca0381, sha256 7546c4c32f0c9e78a7dfb7825b1b3c3ff1727c60d2f0621602e561e488ee62d6)
BibTeX
@misc{dc6af290ca0381,
title = {Quadratic Word Equations with a Linear Side: Polynomial Nielsen Graph Diameter and NP-Completeness — arXiv:2609.21785},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.21785},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6af290ca0381; sha256 7546c4c32f0c9e78a7dfb7825b1b3c3ff1727c60d2f0621602e561e488ee62d6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21785. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The satisfiability problem for word equations asks whether variables can be replaced by words so that the two sides become equal. For regular word equations, in which each variable occurs at most once on each side, satisfiability is NP-complete. For general quadratic word equations, in which each variable occurs at most twice in total, satisfiability is NP-hard, but its membership in NP remains open. We consider an intermediate class: quadratic word equations with a linear side, where each variable occurs at most once on one designated side. We show that the Nielsen graph of an equation $U=V$ in this class, with total length $N=|U|+|V|$, has diameter $O(N^{12})$, measured over reachable pairs of vertices. Together with the known NP-hardness for regular word equations, this result establishes NP-completeness of satisfiability for this class. We also show that each strongly connected component is isomorphic to the length-preserving reachability graph of a regular equation, and that the condensation graph has depth at most $|U|+2|V|$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in cs.CC).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.21785 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T02:30:12.546Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).