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?

Thanks in advance

  • $\begingroup$ I think this is offtopic: should be on Computer Science site: cstheory.stackexchange.com $\endgroup$ – Igor May 22 '13 at 18:07
  • $\begingroup$ SAT Problem is origined from set theory. Besides I didn't even know about cs stackexchange, then thanks :) $\endgroup$ – DanielY May 22 '13 at 18:08
  • 1
    $\begingroup$ 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)? $\endgroup$ – Peter Košinár May 22 '13 at 18:36
  • $\begingroup$ After some thinking I understood your answer :) thank you very much! $\endgroup$ – DanielY May 22 '13 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.