Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses.
Holger DellDieter van MelkebeekPublished in: Parameterized complexity and approximation algorithms (2009)
Keyphrases
- np complete
- computational complexity
- polynomial time complexity
- bounded treewidth
- special case
- satisfiability problem
- np hard
- propositional logic
- least squares
- boolean formula
- decision procedures
- sat problem
- approximation algorithms
- phase transition
- reasoning problems
- data sets
- lower level
- image restoration
- worst case
- cnf formula
- np hardness
- query language
- relational databases
- neural network