Shellability is NP-complete.

Xavier Goaoc Pavel Paták Zuzana Patáková Martin Tancer Uli Wagner

Published in: J. ACM (2019)

Keyphrases

np complete
np hard
randomly generated
satisfiability problem
constraint satisfaction problems
pspace complete
polynomially solvable
computational complexity
conjunctive queries
polynomial time complexity
np complete problems
sat problem
bounded treewidth
databases
phase transition