A simplified NP-complete MAXSAT problem

被引：53
作者：
Raman, V
Ravikumar, B
Rao, SS
机构：
[1] Inst Math Sci, Chennai 600113, India
[2] Univ Rhode Isl, Dept Comp Sci, Kingston, RI 02881 USA
来源：
INFORMATION PROCESSING LETTERS | 1998年 / 65卷 / 01期
关键词：
computational complexity; algorithms;
D O I：
10.1016/S0020-0190(97)00223-8
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
It is shown that the MAX2SAT problem is NP-complete even if every variable appears in at most three clauses. However, if every variable appears in at most two clauses, it is shown that it (and even the general MAXSAT problem) can be solved in linear time. When every variable appears in at most three clauses, we give an exact algorithm for MAXSAT that takes at most 0(3(n/2)n) steps where n is the number of variables. (C) 1998 Published by Elsevier Science B.V.
引用
收藏
页码：1 / 6
页数：6
相关论文
共 10 条
[1]  
GAREY MR, 1979, COMPUTES INTRACTABIL
[2]  
GREY MR, 1976, THEORET COMPUT SCI, V1, P237
[3]   ON THE COMPLEXITY OF THE MAXIMUM SATISFIABILITY PROBLEM FOR HORN FORMULAS [J].
JAUMARD, B ;
SIMEONE, B .
INFORMATION PROCESSING LETTERS, 1987, 26 (01) :1-4
[4]   THE MINIMUM SATISFIABILITY PROBLEM [J].
KOHLI, R ;
KRISHNAMURTI, R ;
MIRCHANDANI, P .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) :275-283
[5]   ONE MORE OCCURRENCE OF VARIABLES MAKES SATISFIABILITY JUMP FROM TRIVIAL TO NP-COMPLETE [J].
KRATOCHVIL, J ;
SAVICKY, P ;
TUZA, Z .
SIAM JOURNAL ON COMPUTING, 1993, 22 (01) :203-210
[6]  
KULLMANN O, 1995, UNPUB SYSTEMATICAL A
[7]   SOLVING SATISFIABILITY IN LESS THAN 2N STEPS [J].
MONIEN, B ;
SPECKENMEYER, E .
DISCRETE APPLIED MATHEMATICS, 1985, 10 (03) :287-295
[8]  
Papadimitriou C. H., 1977, Theoretical Computer Science, V4, P237, DOI 10.1016/0304-3975(77)90012-3
[9]  
SCHIERMEYER I, 1993, P 6 WORKSH COMP SCI, P379
[10]   A SIMPLIFIED NP-COMPLETE SATISFIABILITY PROBLEM [J].
TOVEY, CA .
DISCRETE APPLIED MATHEMATICS, 1984, 8 (01) :85-89
1