Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I've seen a lot of text concerning the first NP-Complete problem, Boolean Satisfiability. I guess I'm confused concerning the language.

It sounds to me as though the problem could be difficult to compute (hence the NP-complete), however it still might be satisfiable. As in, there exists a satisfying mapping of literals. We can't necessarily compute it easily, but it's out there.

In fact, I would guess that the two adjectives really have no relation to each other. But, when working with problems, I am often asked to see whether a set of clauses is satisfiable. Does that mean, Can we compute a satisfying mapping? And by extension, does NP-complete imply that a given CNF setup is unsatisfiable?

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

You're confusing languages and instances of them. A 3SAT formula could be either satisfiable or unsatisfiable. The 3SAT problem is to decide whether a given 3SAT formula is satisfiable. The 3SAT language is the set of all encodings of satisfiable 3SAT formulas. Only the 3SAT language is NP-complete. NP-completeness is a property of languages, not of their instances. If every 3SAT formula were satisfiable (or every one were unsatisfiable) then 3SAT (the language) would be very easy.

share|improve this answer
    
Got it, thanks! –  Alex Chumbley Feb 21 at 3:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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