IEICE Technical Committee Submission System Conference Paper's Information Online Proceedings [Sign in] Tech. Rep. Archives
 Go Top Page Go Previous [Japanese] / [English]

 Paper Abstract and Keywords Presentation 2006-03-23 09:00 Increasing the Success Probability of PPSZ-type Satisfiability TestingKazuo Iwama, Suguru Tamaki (Kyoto Univ.) Abstract (in Japanese) (See Japanese page) (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 \textbf{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 \textbf{PPSZ} should increase. To get this better assignment we use the second algorithm (denoted by \textbf{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 \textbf{PPSZ} with this assignment \$a^*\$ has a better success probability than to continue \textbf{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) (in English) CNF Satisfiability / Probabilistic Algorithm / Complexity / / / / / Reference Info. IEICE Tech. Rep., vol. 105, no. 680, COMP2005-63, pp. 1-6, March 2006. Paper # COMP2005-63 Date of Issue 2006-03-16 (COMP) ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380 Download PDF

 Conference Information Committee COMP Conference Date 2006-03-22 - 2006-03-23 Place (in Japanese) (See Japanese page) Place (in English) The University of Electro-Communications Topics (in Japanese) (See Japanese page) Topics (in English) Paper Information Registration To COMP Conference Code 2006-03-COMP Language English 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 Keyword(4) Keyword(5) Keyword(6) Keyword(7) Keyword(8) 1st Author's Name Kazuo Iwama 1st Author's Affiliation Kyoto University (Kyoto Univ.) 2nd Author's Name Suguru Tamaki 2nd Author's Affiliation Kyoto University (Kyoto Univ.) 3rd Author's Name 3rd Author's Affiliation () 4th Author's Name 4th Author's Affiliation () 5th Author's Name 5th Author's Affiliation () 6th Author's Name 6th Author's Affiliation () 7th Author's Name 7th Author's Affiliation () 8th Author's Name 8th Author's Affiliation () 9th Author's Name 9th Author's Affiliation () 10th Author's Name 10th Author's Affiliation () 11th Author's Name 11th Author's Affiliation () 12th Author's Name 12th Author's Affiliation () 13th Author's Name 13th Author's Affiliation () 14th Author's Name 14th Author's Affiliation () 15th Author's Name 15th Author's Affiliation () 16th Author's Name 16th Author's Affiliation () 17th Author's Name 17th Author's Affiliation () 18th Author's Name 18th Author's Affiliation () Speaker 2 Date Time 2006-03-23 09:00:00 Presentation Time 35 Registration for COMP Paper # IEICE-COMP2005-63 Volume (vol) IEICE-105 Number (no) no.680 Page pp.1-6 #Pages IEICE-6 Date of Issue IEICE-COMP-2006-03-16