Algorithms for four variants of the exact satisfiability problem

作     者：Dahllöf, V Jonsson, P Beigel, R 

作者机构：Linkoping Univ Dept Comp & Informat Sci SE-85183 Linkoping Sweden Temple Univ Dept Comp & Informat Sci Philadelphia PA 19122 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2004年第320卷第2-3期

页      面：373-394页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation, NSF, (CCR-0049019) Directorate for Computer and Information Science and Engineering, CISE, (0049019) Vetenskapsrådet, VR, (221-2000-361) National Graduate School in Computer Science, CUGS 

主　　题：satisfiability SAT exact satisfiability XSAT 3-satisfiability exact 3-satisfiability X3SAT counting counting problem counting models algorithm exact solution exponential-time algorithm computational complexity 

摘      要：We present four polynomial space and exponential time algorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1.1120(n)) (where n is the number of variables) time algorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1.1907(n)) time algorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1.1193(n)) and O(1.2299(n)) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1.1487(n)) time algorithm. We also present an O(1.2190(n)) time algorithm for the general problem of counting the number of models for EXACT SATISFIABILITY;presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix. (C) 2004 Elsevier B.V. All rights reserved.