I am trying to understand the concept of CNF satisfiability, can someone throw some light on

1) what does 3- CNF, 4- CNF etc.. mean?

2) What does yes and no instance mean and can someone provide an example for the same ?

I am learning this subject at school and having hard time gathering basics of this concept.

Any help would be appreciated

  • $\begingroup$ This is a very basic question, which is covered in any textbook on complexity theory and many websites already. This kind of question doesn't work well on Stack Exchange because there's little point in us duplicating information that exists in many other places and because we can't have a discussion with you to help you understand in the descriptions you've already read. $\endgroup$ – David Richerby Nov 17 '14 at 19:35
  • 1
    $\begingroup$ @DavidRicherby thanks for your feedback, will keep in mind to be more descriptive after the ground work from my side $\endgroup$ – Swathi Nov 17 '14 at 22:27
  • $\begingroup$ Great! Hope to see you again soon! $\endgroup$ – David Richerby Nov 17 '14 at 22:38

Let's define the terms:

atom = the same thing you called variable; e.g. "x", "y", "z", etc.

literal = an atom or its negation; e.g "x" or "¬x".

clause = a disjunction of literals; e.g. (x∨y∨¬z∨w).

CNF: A formula is said to be in Conjunctive Normal Form (CNF) if it consists of AND's of several clause. For instance, (x∨y)∧(y∨¬z∨w) is a CNF formula.

The following problem is K-SAT: Given a CNF formula f, in which each clause has exactly K literals, decide whether or not f is satisfiable. That is, whether there is a an assignment to the atoms such that f evaluates to TRUE.

3-SAT and 4-SAT are the special cases of K-SAT problem.

For details, http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.