Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete.
Giorgio AusielloFrancesco CristianoLuigi LauraPublished in: Electron. Colloquium Comput. Complex. (2012)
Keyphrases
- graph isomorphism
- boolean formula
- conjunctive normal form
- sat solvers
- np complete
- graph mining
- conp complete
- subgraph isomorphism
- graph search
- graph databases
- linear constraints
- practical problems
- membership queries
- learning algorithm
- boolean functions
- sat problem
- max sat
- sat instances
- satisfiability problem
- search strategy
- search algorithm