-2
$\begingroup$

Its is known that 3SAT (all clauses have size 3) is NP-complete.

But how about 1SAT (all clauses have size 1), is it also NP-complete? I tried searching for it a lot, but couldnt find any proofs or explanations for the same.

Like 3SAT has 3 clauses, what if I consider just one clause?

Thanks for the help in advance.

$\endgroup$

closed as unclear what you're asking by D.W., Vor, J.-E. Pin, András Salamon, Juho Nov 8 '13 at 23:03

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ 3SAT doesn't have three clauses: it has any number of clauses but each one contains only three literals. Try writing out a formula where each clause has only one literal in it and think about how you'd work out if it's satisfiable or not. $\endgroup$ – David Richerby Oct 31 '13 at 20:50
11
$\begingroup$

$k$-SAT is defined as the problem of finding models (assignments of either true or false to the variables appearing in the formula) to propositional formulas in Conjunctive Normal Form (CNF). A clause is defined as a disjunction of literals (variables that are either in positive or negative form) and a CNF formula is then just a conjunction of clauses.

Thus, as David Richerby already told you, it is not about formulae that have $k$ clauses.

Take the case you mention, 1-SAT. It is trivial to prove that it can be solved in linear time, $O(k)$ with $k$ being the number of clauses: you just assign value true to the propositions that are positive and false otherwise. It is also possible to prove that a formula is unsatisfiable if it appears in two different (unary) clauses in positive and negative form as you are processing the formula.

Krom showed in 1967 that 2-SAT can be solved in polynomial time.

However, 3-SAT has been known since 1972 to be NP-complete (included in Karp's 21 problems) and there is indeed a lot of work on the (2+p)-SAT where random formulae are generated with clauses of length 2 with probability $(1-p)$ and length 3 with probability $p$ showing that there is a clear transition from polynomial to exponential complexity.

$\endgroup$
  • $\begingroup$ Thanks David for the edit. I just made a slight modification. In your text it seems that credit shall be given to Karp for proving that 3-SAT is NP-complete, but this is instead a result by Steve Cook in 1971. I have preserved all your comments and all I did was just to add this. Feel free, of course, to make additional edits $\endgroup$ – Carlos Linares López Nov 2 '13 at 17:02
  • $\begingroup$ That's because it was Karp who first proved that 3SAT is NP-complete! Cook only proved that the satisfiability problem for general Boolean formulas is NP complete. The formulas generated by Cook's reduction aren't in CNF, let alone 3CNF. $\endgroup$ – David Richerby Nov 2 '13 at 21:49
  • 1
    $\begingroup$ You are definitely right! I double-checked that and it was indeed Karp who proved 3SAT to be NP-complete. While "googling" I found an atonishing number of references where it is said "Cook-Levin Theorem: 3SAT is NP-complete". But you are indeed right. Thanks $\endgroup$ – Carlos Linares López Nov 3 '13 at 0:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.