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 |