THE MINIMUM SATISFIABILITY PROBLEM

被引：78

作者：

KOHLI, R

KRISHNAMURTI, R

MIRCHANDANI, P

机构：

[1] SIMON FRASER UNIV, SCH COMP SCI, BURNABY V5A 1S6, BC, CANADA

[2] UNIV PITTSBURGH, JOSEPH M KATZ SCH BUSINESS, PITTSBURGH, PA 15260 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1994年 / 7卷 / 02期

关键词：

MINIMUM SATISFIABILITY; SATISFIABILITY; HEURISTICS; PROBABILISTIC ALGORITHMS; AVERAGE PERFORMANCE; HORN FORMULAS;

D O I：

10.1137/S0895480191220836

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：275 / 283

页数：9

共 6 条

[1] LINEAR-TIME ALGORITHMS FOR TESTING THE SATISFIABILITY OF PROPOSITIONAL HORN FORMULAE. [J].

Dowling, William F. ;

Gallier, Jean H. .

Journal of Logic Programming, 1984, 1 (03) :267-284

[2]

Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048

[3]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[4]

Garey M. R., 1979, COMPUTERS INTRACTIBI

[5] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS [J].

JOHNSON, DS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) :256-278

[6]

KOHLI R, 1989, SIAM J DISCRETE MATH, V2, P508

← 1 →