2

How to prove that a problem is NP complete?

Under "2) Prove it's NP-hard."

This involves getting a known NP-complete problem like SAT (the set of boolean expressions in the form "(A OR B OR C) AND (D OR E OR F) AND ..." where the expression is satisfiable (ie there exists some setting for these booleans which makes the expression true).

The example accidentally implies the format for 3SAT, and it's never actually specified that the formula should be in CNF. I first used this answer when discovering how to prove NP-completeness, and was thrown off since I've heard of SAT and 3SAT but was not completely solid on the definitions.

My edit was too minor, so I'm asking someone who has full editing privileges to make a small change to clear up the confusion.

Improve this question
4
  • 6
    Should you just add your own answer, or put this as a comment in that answer?
    – Krease
    Dec 2, 2013 at 3:47
  • It might be better to either comment on the existing answer, or write a more correct answer instead of editing that one.
    – Makoto
    Dec 2, 2013 at 3:52
  • Uhm, you could flag for moderator attention and explain why you are making the minor edit. I thought that's how it was supposed to work, but I could be wrong.
    – Masked Man
    Dec 2, 2013 at 6:47
  • 1
    No reason to add an answer for such a minor change (the original answer is correct, SAT is just given as an example). Just add a comment if you want.
    – interjay
    Dec 2, 2013 at 9:18

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .