The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems.

Victor Lagerkvist Magnus Wahlström

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

Keyphrases

fine grained
np hard
coarse grained
np complete
constraint satisfaction problems
access control
backtracking search
decision problems
tightly coupled
special case
satisfiability problem
np complete problems
approximation algorithms
constraint propagation
sat problem
search engine
parallel algorithm