1 Attachment(s)

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

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.

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

Thanks for the clarification! : )