# Variation of 3SAT is in NP-Complete

Consider the problem of "K-3SAT", a variation of 3SAT: Given a 3CNF formula O and an integer k, the machine determines whether the formula O has a satisfying assignment in which at most k variables assigned as "true".

I need to prove that it's in NP-Complete by showing a reduction from another known language in NP-Complete (vertex cover, clique, sat, 3sat) to this problem. which one would you suggest?

• Reducing SAT to K-3SAT is trivial: just run the $K-3SAT$ machine with $k$ equal to the number of variables. Thus, K-3SAT is NP-hard. Can you see how to prove it's NP (and thus NP-complete)? – Peter Košinár May 22 '13 at 18:36