The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs

2007/06/14 by Chris Calabro, Russell Impagliazzo, Valentine Kabanets +1 · 5 citations
Computer Science · #Constraint Satisfaction and Optimization #semigroups and automata theory #Logic, Reasoning, and Knowledge

paper · doi:10.1016/j.jcss.2007.06.015

Cited by

• A Linear Algebra Formulation for Boolean Satisfiability Testing
• 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
• Lower bounds for testing graphical models: colorings and\n antiferromagnetic Ising models
• Separating OR, SUM, and XOR Circuits. [europepmc]
• Uniquely Satisfiable d -Regular ( k , s )-SAT Instances. [europepmc]