2 citations · 5 across the 14 of their papers we have counts for
14 papers
The Erdös-Straus Conjecture and Pythagorean Primes
Bernd R. Schuh
The Diophantine equation 4/n=1/x+1/y+1/z for a Pythagorean prime n is split into two independent Diophantine equations, which correspond to two different types of solution. The sol…
Unique polynomial solution of for if
Bernd R. Schuh
Necessary and sufficient conditions for the existence of an integer solution of the diophantine equation with are explicitly given for a,b copri…
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…
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…
Easy/Hard Transition in k-SAT
Bernd R. Schuh
A heuristic model procedure for determining satisfiability of CNF-formulae is set up and described by nonlinear recursion relations for m (number of clauses), n (number of variable…
SAT for pedestrians
Bernd R. Schuh
The aim of this short note is mainly pedagogical. It summarizes some knowledge about Boolean satisfiability (SAT) and the P=NP? problem in an elementary mathematical language. A co…
Phase Transition in Unrestricted Random SAT
Bernd R. Schuh
For random CNF formulae with m clauses, n variables and an unrestricted number of literals per clause the transition from high to low satisfiability can be determined exactly for l…
A Real World Mechanism for Testing Satisfiability in Polynomial Time
Bernd R. Schuh
Whether the satisfiability of any formula F of propositional calculus can be determined in polynomial time is an open question. I propose a simple procedure based on some real worl…
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…
Algebraic Properties of Propositional Calculus
Bernd R. Schuh
In this short note we relate some known properties of propositional calculus to purely algebraic considerations of a Boolean algebra. Classes of formulas of propositional calculus…