Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou studied in [Gopalan et al., ICALP2006] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on connectivity problems in Schaefer's framework [Schaefer, STOC1978]. A set S of logical relations is Schaefer if all relations in ... more >>>

The well known dichotomy conjecture of Feder and Vardi states that for every finite family Γ of constraints CSP(Γ) is either polynomially solvable or NP-hard. Bulatov and Jeavons re- formulated this conjecture in terms of the properties of the algebra P ol(Γ), where the latter is the collection of those ... more >>>