-1
$\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.

Improve this question
$\endgroup$
1
  • 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
    Commented Oct 31, 2013 at 20:50

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 2, 2013 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
    Commented Nov 2, 2013 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
    Commented Nov 3, 2013 at 0:23

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