| A Simplified NP-complete MAXSAT Problem (2001) | |||||||||||||||
Abstract | |||||||||||||||
| 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 O(3 n) steps where n is the number of variables. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||