THE MINIMUM SATISFIABILITY PROBLEM

作     者：KOHLI, R KRISHNAMURTI, R MIRCHANDANI, P 

作者机构：SIMON FRASER UNIV SCH COMP SCI BURNABY V5A 1S6 BC CANADA UNIV PITTSBURGH JOSEPH M KATZ SCH BUSINESS PITTSBURGH PA 15260 USA 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1994年第7卷第2期

页      面：275-283页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：MINIMUM SATISFIABILITY SATISFIABILITY HEURISTICS PROBABILISTIC ALGORITHMS AVERAGE PERFORMANCE HORN FORMULAS 

摘      要：This paper shows that a minimization version of satisfiability is strongly NP-hard, even if each clause contains no more than two literals and/or each clause contains at most one unnegated variable. The worst-case and average-case performances of greedy and probabilistic greedy heuristics for the problem are examined, and tight upper bounds on the performance ratio in each case are developed.