Collapsibility to a Subcomplex of a Given Dimension is NP-Complete.

Giovanni Paolini

Published in: Discret. Comput. Geom. (2018)

Keyphrases

np complete
np hard
randomly generated
constraint satisfaction problems
phase transition
satisfiability problem
computational complexity
polynomially solvable
conjunctive queries
objective function
polynomial time complexity
pspace complete
data sets
data structure
temporal dimension
multiple dimensions