Jump to ContentJump to Main Navigation
Computational Complexity and Statistical Physics$
Users without a subscription are not able to see the full content.

Allon Percus, Gabriel Istrate, and Cristopher Moore

Print publication date: 2005

Print ISBN-13: 9780195177374

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780195177374.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 17 October 2021

The Phase Transition in the Random HornSAT Problem

The Phase Transition in the Random HornSAT Problem

Chapter 9 The Phase Transition in the Random HornSAT Problem
Computational Complexity and Statistical Physics

Demetrios D. Demopoulos

Moshe Y. Vardi

Oxford University Press

This chapter presents a study of the satisfiability of random Horn formulas and a search for a phase transition. In the past decade, phase transitions or sharp thresholds, have been studied intensively in combinatorial problems. Although the idea of thresholds in a combinatorial context was introduced as early as 1960 [147], in recent years it has been a major subject of research in the communities of theoretical computer science, artificial intelligence, and statistical physics. As is apparent throughout this volume, phase transitions have been observed in numerous combinatorial problems, both for the probability that an instance of a problem has a solution and for the computational cost of solving an instance. In a few cases (2-SAT, 3-XORSAT, 1-in-k SAT) the existence and location of these phase transitions have also been formally proven [7, 94, 101, 131, 156, 202]. The problem at the center of this research is that of 3-satisfiability (3-SAT). An instance of 3-SAT consists of a conjunction of clauses, where each clause is a disjunction of three literals. The goal is to find a truth assignment that satisfies all clauses. The density of a 3-S AT instance is the ratio of the number of clauses to the number of Boolean variables. We call the number of variables the size of the instance. Experimental studies [110, 395, 397, 466, 469] have shown that there is a shift in the probability of satisfiability of random 3-S AT instances, from 1 to 0, located at around density 4.27 (this is also called the crossover point}. So far, in spite of much progress in obtaining rigorous bounds on the threshold location, highlighted in the previous chapters, there is no mathematical proof of a phase transition taking place at that density [1, 132, 177]. Experimental studies also show a peak of the computational complexity around the crossover point. In Kirkpatrick and Selman [319], finite-size scaling techniques were used to suggest a phase transition at the crossover point. Later, in Coafra et al. [96], experiments showed that a phase transition of the running time from polynomial in the instance size to exponential is solver-dependent, and for several different solvers this transition occurs at a density lower than the crossover point.

Keywords:   AC-matching, NP-complete, Poisson random hypergraph, automata theory, binary-tree automaton, critical exponent, digraph reachability analysis, finite automata, linear regression, random digraph

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .