[HTML][HTML] XSAT and NAE-SAT of linear CNF classes
S Porschen, T Schmidt, E Speckenmeyer… - Discrete Applied …, 2014 - Elsevier
Abstract XSAT and NAE-SAT are important variants of the propositional satisfiability problem
(SAT). XSAT contains all CNF formulas that can be satisfied by setting exactly one literal in …
(SAT). XSAT contains all CNF formulas that can be satisfied by setting exactly one literal in …
The Lovász local lemma and satisfiability
H Gebauer, RA Moser, D Scheder, E Welzl - … on the Occasion of His 60th …, 2009 - Springer
We consider boolean formulas in conjunctive normal form (CNF). If all clauses are large, it
needs many clauses to obtain an unsatisfiable formula; moreover, these clauses have to …
needs many clauses to obtain an unsatisfiable formula; moreover, these clauses have to …
Computational complexity of SAT, XSAT and NAE-SAT for linear and mixed Horn CNF formulas
T Schmidt - 2010 - kups.ub.uni-koeln.de
The Boolean conjunctive normal form (CNF) satisfiability problem, called SAT for short, gets
as input a CNF formula and has to decide whether this formula admits a satisfying truth …
as input a CNF formula and has to decide whether this formula admits a satisfying truth …
Unsatisfiable linear CNF formulas are large and complex
D Scheder - arXiv preprint arXiv:0905.1587, 2009 - arxiv.org
We call a CNF formula linear if any two clauses have at most one variable in common. We
show that there exist unsatisfiable linear k-CNF formulas with at most 4k^ 2 4^ k clauses …
show that there exist unsatisfiable linear k-CNF formulas with at most 4k^ 2 4^ k clauses …
[PDF][PDF] Algorithms and Extremal Properties of SAT and CSP
DA Scheder - 2011 - research-collection.ethz.ch
This thesis treats algorithmic and combinatorial aspects of Boolean satisfiability and
constraint satisfaction. Satisfiability is the problem of deciding whether a given propositional …
constraint satisfaction. Satisfiability is the problem of deciding whether a given propositional …
[PDF][PDF] Unsatisfiable linear CNF formulas are large, and difficult to construct explicitely
D Scheder - CoRR abs/0905.1587, 2009 - Citeseer
arXiv:0905.1587v1 [cs.DM] 11 May 2009 Page 1 arXiv:0905.1587v1 [cs.DM] 11 May 2009
Unsatisfiable Linear CNF Formulas Are Large, and Difficult to Construct Explicitely Dominik …
Unsatisfiable Linear CNF Formulas Are Large, and Difficult to Construct Explicitely Dominik …