Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By ILikeSerena

Math Help - The 3-SAT vs. 3-CNF problem (NP Completeness in Combinatorial Optimization)

  1. #1
    Newbie
    Joined
    Mar 2013
    From
    Washington
    Posts
    9
    Thanks
    2

    Thumbs up The 3-SAT vs. 3-CNF problem (NP Completeness in Combinatorial Optimization)

    Hi there.

    I'm doing some reading for a course and I can't figure out if the 3-SAT problem is the same as the 3-CNF problem.

    Specifically, I have a pretty standard algorithms textbook (Cormen, et al) that calls what I think is 3-SAT "3-conjuntive normal form" or 3-CNF.

    In a nutshell, 3-CNF is a set of 3 literals separated by OR and connected by AND. In other words, the book says:

    (x1 V x2 V x3) & (x3 V x4 V x5) & (~x6 V x7 V ~x8)

    is 3-CNF. Is this fundamentally different than 3-SAT?

    Is this the same thing or are algorithm people not using the same language as combinatorial people? So far this is the best description of SAT I have found in any of my books. Searches on google have been unfruitful.

    Thank you!

    Eric
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: The 3-SAT vs. 3-CNF problem (NP Completeness in Combinatorial Optimization)

    Quote Originally Posted by MooMooMoo View Post
    Hi there.

    I'm doing some reading for a course and I can't figure out if the 3-SAT problem is the same as the 3-CNF problem.

    Specifically, I have a pretty standard algorithms textbook (Cormen, et al) that calls what I think is 3-SAT "3-conjuntive normal form" or 3-CNF.

    In a nutshell, 3-CNF is a set of 3 literals separated by OR and connected by AND. In other words, the book says:

    (x1 V x2 V x3) & (x3 V x4 V x5) & (~x6 V x7 V ~x8)

    is 3-CNF. Is this fundamentally different than 3-SAT?

    Is this the same thing or are algorithm people not using the same language as combinatorial people? So far this is the best description of SAT I have found in any of my books. Searches on google have been unfruitful.

    Thank you!

    Eric
    Hi MooMooMoo!

    Wikipedia has an article about it here.

    In short a 3-SAT problem is a 3-CNF satisfiability problem.
    A SAT problem is to figure out whether there is an assignment of the booleans that make the expression true.
    A 3-SAT specifically restricts the type of problem to 3-CNF expressions.

    It is not clear to me what a 3-CNF problem would be, which could be anything involving 3-CNF expressions.
    Thanks from MooMooMoo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2013
    From
    Washington
    Posts
    9
    Thanks
    2

    Re: The 3-SAT vs. 3-CNF problem (NP Completeness in Combinatorial Optimization)

    Thanks for the clarification! : )
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 4th 2011, 10:05 AM
  2. Replies: 0
    Last Post: August 20th 2010, 12:15 PM
  3. Combinatorial problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 13th 2008, 07:22 PM
  4. Replies: 0
    Last Post: November 6th 2007, 03:05 PM
  5. Problem on sufficiency , completeness and ancillarity
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 9th 2007, 01:49 PM

Search Tags


/mathhelpforum @mathhelpforum