Hard satisfiable formulas for splittings by linear combinations.
Dmitry ItsyksonAlexander KnopPublished in: Electron. Colloquium Comput. Complex. (2017)
Keyphrases
- linear combination
- random sat
- truth assignment
- basis functions
- phase transition
- cnf formula
- randomly chosen
- small number
- propositional formulas
- satisfiability problem
- sat problem
- randomly generated
- random instances
- sparse coding
- conjunctive normal form
- sparse approximation
- propositional logic
- weighted sum
- max sat
- low order
- np complete
- sat instances
- constraint satisfaction problems
- feature vectors