1 citations · 2 across the 5 of their papers we have counts for
7 papers
Balanced incomplete block designs and exact satisfiability
Bernd. R. Schuh
The paper explores the correspondence between balanced incomplete block designs (BIBD) and certain linear CNF formulas by identifying the points of a block design with the clauses…
Sub-exponential complexity of regular linear CNF formulas
Bernd R. Schuh
The study of regular linear conjunctive normal form (LCNF) formulas is of interest because exact satisfiability (XSAT) is known to be NP-complete for this class of formulas. In a r…
Sub-exponential Upper Bound for #XSAT of some CNF Classes
Bernd Schuh
We derive an upper bound on the number of models for exact satisfiability (XSAT) of arbitrary CNF formulas F. The bound can be calculated solely from the distribution of positive a…
XSAT of Linear CNF Formulas
Bernd. R. Schuh
Open questions with respect to the computational complexity of linear CNF formulas in connection with regularity and uniformity are addressed. In particular it is proven that any l…
A criterion for "easiness" of certain SAT problems
Bernd R. Schuh
A generalized 1-in-3SAT problem is defined and found to be in complexity class P when restricted to a certain subset of CNF expressions. In particular, 1-in-kSAT with no restrictio…
Logical Primes, Metavariables and Satisfiability
Bernd R. Schuh
For formulas F of propositional calculus I introduce a "metavariable" MF and show how it can be used to define an algorithm for testing satisfiability. MF is a formula which is tru…