Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses.
Holger DellDieter van MelkebeekPublished in: J. ACM (2014)
Keyphrases
- np complete
- computational complexity
- polynomial time complexity
- satisfiability problem
- bounded treewidth
- special case
- worst case
- phase transition
- approximation algorithms
- lower level
- np hard
- hierarchical structure
- tree structure
- decision procedures
- cnf formula
- conjunctive queries
- propositional logic
- sat problem
- boolean formula
- neural network