The Complexity of Promise SAT on Non-Boolean Domains.

Alex Brandts Marcin Wrochna Stanislav Zivný

Published in: ACM Trans. Comput. Theory (2021)

Keyphrases

satisfiability problem
computational complexity
worst case
application domains
real world
computational cost
decision problems
real valued
variable ordering
boolean formula
complex domains
multi valued
sat problem
search problems
sat solvers
boolean functions
bayesian networks
decision trees