2014/11/11 by Bernd Schuh, Bernd R. Schuh, Schuh, Bernd R.
Business, Management and Accounting · Computer Science · Mathematics · #Business Process Modeling and Analysis #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Multi-Agent Systems and Negotiation #cs.CC #math.LO
paper · pdf · doi:10.48550/arxiv.1411.2901
11 pages, 6 figures
arxiv created 2014/11/11 · openalex publication_date 2014/11/11 · arxiv updated 2014/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 variables) and clause filling k. The system mimicked by the recursion undergoes a sharp transition from bounded running times (easy) to uncontrolled runaway behaviour (hard). Thus the parameter space turns out to be separated into regions with qualitatively different efficiency of the model procedure. The transition results from a competition of exponential blow up by branching versus growing number of orthogonal clauses.