2 citations · 5 across the 14 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.CC2017
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…
cs.CC2017
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…
cs.CC2017
Polynomial time estimates for #SAT
Bernd R. Schuh
Limits on the number of satisfying assignments for CNS instances with n variables and m clauses are derived from various inequalities. Some bounds can be calculated in polynomial t…