Clique Homology is -hard.

Nat Commun

Instituto de Ciencias Matemáticas, Madrid, Spain.

Published: November 2024

We address the long-standing question of the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology, posed by Kaibel and Pfetsch over twenty years ago. We show that decision problem is -hard and the exact counting version is -hard. In fact, we strengthen this by showing that the problems remains hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and algebraic topology. As we discuss, a version of the problems satisfying a suitable promise and certain constraints is contained in and , respectively. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.

Download full-text PDF

Source
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC11561080PMC
http://dx.doi.org/10.1038/s41467-024-54118-zDOI Listing

Publication Analysis

Top Keywords

simplicial complexes
8
topological data
8
data analysis
8
clique homology
4
homology -hard
4
-hard address
4
address long-standing
4
long-standing question
4
question computational
4
computational complexity
4

Similar Publications

Want AI Summaries of new PubMed Abstracts delivered to your In-box?

Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!