I\'ve seen a lot of text concerning the first NP-Complete problem, Boolean Satis

Question

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.