Division of Informatics
Forrest Hill & 80 South Bridge

Research Paper #679
Title:	The Sat Phase Transition
Authors:	Gent,I; Walsh,T
Date:	Jan 1994
Presented:	Submitted to ECAI-94
Keywords:
Abstract:	We describe a detailed experimental investigation of the phase transition for several different classes of randomly generated satisfiability problems. We observe a remarkable consistency of features in the phase transition despite the presence in some of the problem classes of clauses of mixed lengths. For instance, each of the problem classes considered has a sharp transition from satisfiable to unsatisfiable problems at a critical value. In addition, there is a common easy-hard-easy pattern in the difficulty of the problems, with the hardest problems being associated with the phase transition. However, the difficulty of problems of mixed clause lengths is much more variable that that of fixed clause length. Indeed, whilst the median difficulty of random problems of mixed clause lengths can be orders of magnitude easier than that of equivalently sized problems of fixed clause length. Such very hard random problems may be of considerable practical and theoretical use in analysing algorithm performance.
Download:	POSTSCRIPT COPY

Division of InformaticsForrest Hill & 80 South Bridge