Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 50 min ago
PreprintCC BY 4.0arXiv

PL Recognition After Two S2× S2 Stabilisations is PSPACE-Hard

  • Rhuaidi Antonio Burke
Open at sourcePDFDOICite

Abstract

Let Z be any fixed closed connected PL $4$-manifold. We give a polynomial-time many-to-one reduction from the compressed word problem in Thompson's group F to fixed-target recognition of Z#2(S2× S2). Once a finite triangulation of Z has been fixed, the construction sends a straight-line program A to a closed triangulated PL $4$-manifold XA,Z such that val(A)=1 in F if and only if XA,Z is PL-homeomorphic to Z#2(S2× S2). Since the compressed word problem in F is PSPACE-complete, every such recognition problem is PSPACE-hard. In particular, fixed-target recognition of #n(S2× S2) is PSPACE-hard for every fixed n≥2.

Related

  1. Arc Kayles is PSPACE-complete
    Édouard Bonnet
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The Two-Level Poset Game is PSPACE-Complete
    Kengo Hashimoto
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. One Polynomial Field for Every Euler Step and the Flow: Polynomial Dynamics for P and PSPACE
    Olivier Bournez
    arXivPreprintarXiv licenceFull textDynamical systemsarXiv
  4. Hard Diagrams of Split Links
    Corentin Lunel, Arnaud de Mesmay, Jonathan Spreer
    Discrete and Computational GeometryPeer-reviewedLicence not statedFull textGeometry & topologyHAL
  5. Fluid dynamic limit of Boltzmann equation for granular hard-spheres in a nearly elastic regime
    Ricardo J. Alonso, Bertrand Lods, Isabelle Tristani
    Mémoires de la Société mathématique de FrancePeer-reviewedLicence not statedFull text16 citedGeneral mathematicsOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{burke2026recognition,
  title = {{PL Recognition After Two $S^2\times S^2$ Stabilisations is PSPACE-Hard}},
  author = {Rhuaidi Antonio Burke},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.15890},
  eprint = {2609.15890},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.15890},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - PL Recognition After Two S^2× S^2 Stabilisations is PSPACE-Hard
AU  - Rhuaidi Antonio Burke
PY  - 2026
DA  - 2026/09/14
PB  - arXiv
DO  - 10.48550/arxiv.2609.15890
UR  - https://arxiv.org/abs/2609.15890
AB  - Let Z be any fixed closed connected PL $4$-manifold. We give a polynomial-time many-to-one reduction from the compressed word problem in Thompson's group F to fixed-target recognition of Z#_2(S^2× S^2). Once a finite triangulation of Z has been fixed, the construction sends a straight-line program A to a closed triangulated PL $4$-manifold X_A,Z such that val(A)=1 in F if and only if X_A,Z is PL-homeomorphic to Z#_2(S^2× S^2). Since the compressed word problem in F is PSPACE-complete, every such recognition problem is PSPACE-hard. In particular, fixed-target recognition of #_n(S^2× S^2) is PSPACE-hard for every fixed n≥2.
ER  -