Results 1 to 1 of 1

Thread: Boolean satisfiability and NP-Completness

  1. #1
    Jan 2006

    Boolean satisfiability and NP-Completness

    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
    Last edited by SkanderH; Feb 5th 2006 at 10:34 PM. Reason: mistakes
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. FOL satisfiability of a sentence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jun 12th 2011, 08:57 AM
  2. More Boolean
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 21st 2009, 03:17 PM
  3. Boolean algebra help
    Posted in the Math Topics Forum
    Replies: 6
    Last Post: Nov 21st 2009, 02:50 PM
  4. Boolean Function
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 21st 2009, 02:40 PM
  5. Boolean Ring
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Oct 18th 2009, 02:19 PM

Search Tags

/mathhelpforum @mathhelpforum