Exploiting partial knowledge of satisfying assignments (Q2643304)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Exploiting partial knowledge of satisfying assignments |
scientific article |
Statements
Exploiting partial knowledge of satisfying assignments (English)
0 references
23 August 2007
0 references
Recently Schöning has shown that a simple local-search algorithm for 3SAT achieves the currently best upper bound, i.e., an expected time of 1.334n. In this paper, we show that this algorithm can be modified to run much faster if there is some kind of imbalance in satisfying assignments and we have a (partial) knowledge about that.
0 references
CNF satisfiability
0 references
probabilistic algorithm
0 references
NP-complete problem
0 references
