Cheap and Secure Web Hosting Provider : See Now

[Solved]: Does NP-Complete imply non-satisfiability?

, , No Comments
Problem Detail: 

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?

Asked By : Alex Chumbley

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback