Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete.
Giorgio AusielloFrancesco CristianoPaolo FantozziLuigi LauraPublished in: ICTCS (2020)
Keyphrases
- graph isomorphism
- boolean formula
- conjunctive normal form
- sat solvers
- np complete
- subgraph isomorphism
- conp complete
- graph search
- graph mining
- membership queries
- graph data
- graph databases
- boolean functions
- search tree
- practical problems
- linear constraints
- binary decision diagrams
- satisfiability problem
- sat instances
- orders of magnitude
- machine learning
- pattern mining
- knowledge compilation