Exact satisfiability,a natural extension of set partition,and its average case behavior |
| |
Authors: | John W Rosenthal Ewald Speckenmeyer Rainer Kemp |
| |
Affiliation: | (1) Present address: Mathematisches Institut/Abt, für Informatik, Heinrich-Heine Universität, Universitätsstr. 1, D-4000 Düsseldorf 1, Germany;(2) Department of Mathematics and Computer Science, Ithaca College, 14850 Ithaca, New York, USA;(3) FB Informatik, Universität Dortmund, Postfach 500500, D-4600 Dortmund 50, Germany;(4) Fachbereich 20-Angewandte Informatik, Johann Wolfgang Goethe-Universität, Postfach 111932, D-6000 Frankfurt/M. 11, Germany |
| |
Abstract: | The problem of determining whether a Boolean formula in conjunctive normal form is satisfiable in such a way that in each clause exactly one literal is set true, and all the other literals are set false is called the exact satisfiability problem. The exact satisfiability problem is well known to be NP-complete 5] and it contains the well known set partitioning problem as a special case. We study here the average time complexity of a simple backtracking strategy for solving the exact satisfiability problem under two probability models, the constant density model and the constant degree model. For both models we present results sharply separating classes of instances solvable in low degree polynomial time in the average from classes for which superpolynomial or exponential time is needed in the average. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|