Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOOLEAN SATISFIABILITY ALGORITHM:
Reports tagged with Boolean satisfiability algorithm:
TR15-192 | 26th November 2015
Ruiwen Chen, Rahul Santhanam

#### Satisfiability on Mixed Instances

The study of the worst-case complexity of the Boolean Satisfiability (SAT) problem has seen considerable progress in recent years, for various types of instances including CNFs \cite{PPZ99, PPSZ05, Sch99, Sch05}, Boolean formulas \cite{San10} and constant-depth circuits \cite{IMP12}. We systematically investigate the complexity of solving {\it mixed} instances, where different parts ... more >>>

ISSN 1433-8092 | Imprint