2012/04/07 by Bernd Schuh, Bernd R. Schuh, Schuh, Bernd R.
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Model-Driven Software Engineering Techniques #Multi-Agent Systems and Negotiation #cs.CC #math.LO
paper · pdf · doi:10.48550/arxiv.1204.1656
14 pages
arxiv created 2012/04/07 · openalex publication_date 2012/04/07 · arxiv updated 2012/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 large n. The critical density m/n turns out to be strongly n-dependent, ccr = ln(2)/(1-p)^n, where pn is the mean number of positive literals per clause.This is in contrast to restricted random SAT problems (random K-SAT), where the critical ratio m/n is a constant. All transition lines are calculated by the second moment method applied to the number of solutions N of a formula. In contrast to random K-SAT, the method does not fail for the unrestricted model, because long range interactions between solutions are not cut off by disorder.