Using clausal graphs to determine the computational complexity of k-bounded positive one-in-three SAT.
Richard DenmanStephen FosterPublished in: Discret. Appl. Math. (2009)
Keyphrases
- computational complexity
- np complete
- positive and negative
- search algorithm
- satisfiability problem
- boolean satisfiability
- bounded treewidth
- high computational complexity
- sat problem
- graph databases
- search strategies
- sat solvers
- graph theory
- theorem proving
- graph representation
- memory requirements
- knowledge compilation
- computationally efficient
- decision procedures
- stochastic local search
- random walk
- logic programming