A question about boolean satisfiability and NP-completness:
The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. An instance of the problem is defined by a Boolean expression written using only AND, OR, NOT, variables, and parentheses. The question is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?
All web sites and textbooks state that SAT is NP-complete.
My question is what is the NP-complete problem:
Just ansewring the SAT problem Yes or No?
Or ansewring the SAT problem and giving a solution in the Yes case?
I am asking about the most general case of SAT written in CNF


LinkBack URL
About LinkBacks