NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY

被引：1

作者：

Zhou, Junping ^{[1
]}

Su, Weihua ^{[1
]}

Wang, Jianan ^{[1
]}

机构：

[1] NE Normal Univ, Sch Comp Sci, Changchun 130117, Peoples R China

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2014年 / 25卷 / 06期

基金：

中国国家自然科学基金;

关键词：

#XSAT; upper bound; resolution principle; common literals principle; RANDOM CONSTRAINT SATISFACTION; ALGORITHMS; KNAPSACK;

D O I：

10.1142/S0129054114500270

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The counting exact satisfiablity problem (#XSAT) is a problem that computes the number of truth assignments satisfying only one literal in each clause. This paper presents an algorithm that solves the #XSAT problem in O(1.1995(n)), which is faster than the best algorithm running in O(1.2190(n)), where n denotes the number of variables. To increase the efficiency of the algorithm, a new principle, called common literals principle, is addressed to simplify formulae. This allows us to further eliminate literals. In addition, we firstly apply the resolution principles into solving #XSAT problem, and therefore it improves the efficiency of the algorithm further.

引用

页码：667 / 678

页数：12

共 17 条

[1] New algorithms for Exact Satisfiability [J].

Byskov, JM ;

Madsen, BA ;

Skjernaa, B .

THEORETICAL COMPUTER SCIENCE, 2005, 332 (1-3) :515-541

[2] Algorithms for four variants of the exact satisfiability problem [J].

Dahllöf, V ;

Jonsson, P ;

Beigel, R .

THEORETICAL COMPUTER SCIENCE, 2004, 320 (2-3) :373-394

[3]

Dahllöf V, 2002, SIAM PROC S, P292

[4]

Fomin Fedor V., 2010, EXACT EXPONENTIAL AL

[5]

Kulikov A, 2005, J MATH SCI, V126, P1195

[6]

Li X, 2007, LECT NOTES COMPUT SC, V4484, P624

[7] On exponential time lower bound of Knapsack under backtracking [J].

Li, Xin ;

Liu, Tian .

THEORETICAL COMPUTER SCIENCE, 2010, 411 (16-18) :1883-1888

[8] Derandomizing the HSSW Algorithm for 3-SAT [J].

Makino, Kazuhisa ;

Tamaki, Suguru ;

Yamamoto, Masaki .

ALGORITHMICA, 2013, 67 (02) :112-124

[9]

Park J.D., 2002, P UAI, P388

[10]

Porschen S, 2005, LECT NOTES COMPUT SC, V3381, P278

← 1 2 →