The phase transition in random Horn satisfiability and its algorithmic implications
| dc.creator | Istrate, Gabriel | |
| dc.date | 1999-12-01 | |
| dc.date.accessioned | 2026-07-07T03:24:28Z | |
| dc.date.available | 2026-07-07T03:24:28Z | |
| dc.description | Let c>0 be a constant, and $Φ$ be a random Horn formula with n variables and $m=c\cdot 2^{n}$ clauses, chosen uniformly at random (with repetition) from the set of all nonempty Horn clauses in the given variables. By analyzing \PUR, a natural implementation of positive unit resolution, we show that $\lim_{n\goesto \infty} \PR ({$Φ$ is satisfiable})= 1-F(e^{-c})$, where $F(x)=(1-x)(1-x^2)(1-x^4)(1-x^8)... $. Our method also yields as a byproduct an average-case analysis of this algorithm. | |
| dc.description | 26 pages. Journal version of papers in AIM'98, SODA'99. Submitted to Random Structures and Algorithms | |
| dc.identifier | https://arxiv.org/abs/cs/9912001 | |
| dc.identifier | http://arxiv.org/abs/cs/9912001 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33336 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.2;I.1.2;G.3 | |
| dc.title | The phase transition in random Horn satisfiability and its algorithmic implications | |
| dc.type | text |