|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The phase transition in random Horn satisfiability and its algorithmic implications | | Gabriel Istrate
; | | Date: |
1 Dec 1999 | | Subject: | Data Structures and Algorithms; Computational Complexity ACM-class: F.2.2;I.1.2;G.3 | cs.DS cs.CC | | Abstract: | Let c>0 be a constant, and $Phi$ be a random Horn formula with n variables and $m=ccdot 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_{ngoesto infty} PR ({$Phi$ 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. | | Source: | arXiv, cs.DS/9912001 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER