๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A simplified NP-complete MAXSAT problem

โœ Scribed by Venkatesh Raman; B. Ravikumar; S.Srinivasa Rao

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
639 KB
Volume
65
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

It is shown that the MAXZSAT 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( @*n) steps where II is the number of variables. @

๐Ÿ“œ SIMILAR VOLUMES

An NP-complete matching problem
An NP-complete matching problem
โœ David A. Plaisted; Samuel Zaks ๐Ÿ“‚ Article ๐Ÿ“… 1980 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 847 KB
NP-complete scheduling problems
NP-complete scheduling problems
โœ J.D. Ullman ๐Ÿ“‚ Article ๐Ÿ“… 1975 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 423 KB

We show that the problem of finding an optimal schedule for a set of jobs is NPcomplete even in the following two restricted cases. (1) All jobs require one time unit. (2) All jobs require one or two time units, and there are only two processor resolving (in the negative a conjecture of R. L. Grah

The STO problem is NP-complete
The STO problem is NP-complete
โœ P. Krysta; L. Pacholski ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 233 KB

We prove that the problem STO of deciding whether or not a finite set E of term equations is subject to occur-check is in NP. E is subject to occur-check if the execution of the Martelli-Montanari unification algorithm gives for input E a set E โˆช {x = t}, where t = x and x appears in t. Apt et al. (