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

• Mar 2nd 2013, 12:45 AM
MooMooMoo
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
• Mar 2nd 2013, 03:54 AM
ILikeSerena
Re: The 3-SAT vs. 3-CNF problem (NP Completeness in Combinatorial Optimization)
Quote:

Originally Posted by MooMooMoo
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.
• Mar 2nd 2013, 10:13 AM
MooMooMoo
Re: The 3-SAT vs. 3-CNF problem (NP Completeness in Combinatorial Optimization)
Thanks for the clarification! : )