A simplified NP-complete satisfiability problem

A simplified NP-complete MAXSAT problem

✍ Venkatesh Raman; B. Ravikumar; S.Srinivasa Rao 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 639 KB

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

The k-SATISFIABILITY problem remains NP-

The k-SATISFIABILITY problem remains NP-complete for dense families

✍ Ingo Schiermeyer 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 228 KB

We consider the ~ATISFIABILITY problem (~-SAT): Given a family F of n clauses cl, .\_, , c, in conjunctive normal form, each consisting of k literals corresponding to k different variables of a set of r 2 k 2 1 boolean variables, is F satisfiable? By k-SAT@ no) we denote the k-SAT problem restricted

An NP-complete matching problem

✍ David A. Plaisted; Samuel Zaks 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 847 KB

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

✍ 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. (

Certain NP-complete matching problems

✍ G. Loizou 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 311 KB