The Satisfiability Threshold for Non-Uniform Random 2-SAT

Tobias Friedrich, Ralf Rothenberger

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worst-case hardness lies at the core of computational complexity theory, for exa…