| Presentation | 2006-03-23 Increasing the Success Probability of PPSZ-type Satisfiability Testing Kazuo IWAMA, Suguru TAMAKI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Recently, [Iwama, Tamaki, SODA04] gave a new worst-case upper bound for 3SAT by modifying the PPSZ-type algorithm in [Paturi et. al., FOCS98] by making use of the local-search-type one in [Schoning, Algorithmica 02]. We propose a different kind of modification in this paper. Recall that the analysis of the first algorithm (denoted by PPSZ) assumes that each bit of the initial assignment coincides that of a satisfying assignment with probability one half. Our idea is that if we can increase this probability, i.e., if we can use a "better" initial assignment, then the success probability of PPSZ should increase. To get this better assignment we use the second algorithm (denoted by SCH). Note that the local search starts with a random assignment and gradually approaches to a satisfying assignment z. In the middle of this process, there should be the moment that the current assignment a^* is close to z and to use PPSZ with this assignment a^* has a better success probability than to continue SCH. In this paper we prove that this conjecture is true under some assumption on the uniformity of probability. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | CNF Satisfiability / Probabilistic Algorithm / Complexity |
| Paper # | COMP2005-63 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2006/3/16(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Increasing the Success Probability of PPSZ-type Satisfiability Testing |
| Sub Title (in English) | |
| Keyword(1) | CNF Satisfiability |
| Keyword(2) | Probabilistic Algorithm |
| Keyword(3) | Complexity |
| 1st Author's Name | Kazuo IWAMA |
| 1st Author's Affiliation | School of Informatics, Kyoto University() |
| 2nd Author's Name | Suguru TAMAKI |
| 2nd Author's Affiliation | School of Informatics, Kyoto University |
| Date | 2006-03-23 |
| Paper # | COMP2005-63 |
| Volume (vol) | vol.105 |
| Number (no) | 680 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |