Lecture Notes on Satisfiability and 3SAT

Introduction to Satisfiability

• Satisfiability Problem: Given a boolean formula in conjunctive normal form (CNF), determine if there is a satisfying truth assignment.
• Boolean Formula in CNF:
  • Composed of Boolean variables or their negations (literals).
  • Includes clauses connected by logical OR operations.
  • Example clause: x_1 or not x_2 or x_3.
  • Formula is true if all clauses are true (conjunction of disjunctions).

Special Case: 3SAT

• 3SAT Problem: A specific case of satisfiability where each clause contains exactly 3 literals.
  • Example clauses for 3SAT:
    • not x_1 or x_2 or x_3 (1st clause)
    • x_1 or not x_2 or x_3 (2nd clause)
    • x_1 or x_2 or x_3 (3rd clause)
    • not x_1 or not x_2 or not x_3 (4th clause)
• Satisfying Truth Assignment Example:
  • Set x_1 = true, x_2 = true, x_3 = false:
    • 1st clause satisfied (x_2 is true)
    • 2nd clause satisfied (x_1 is true)
    • 3rd clause satisfied (both x_1 and x_2 are true)
    • 4th clause satisfied (not x_3 is true)

Reduction from 3SAT to Independent Set

• Reduction Concept: 3SAT can be Karp reduced to the Independent Set problem.
  • Use gadget construction to show equivalence.
• Graph Construction:
  • For each clause in the 3SAT formula, create 3 vertices connected in a triangle.
    • Ensures that only one vertex can be selected from each triangle (clause).

Ensuring Consistency in Choices

• Choice Consistency: Avoid selecting both a variable and its negation.
  • Connect vertices for x_i and not x_i by an edge.
  • This ensures choices align with possible truth assignments.

Choosing the Value of k

• Value of k: Set k to the number of clauses in the formula.
  • Ensures at least k vertices must be picked from the independent set.
• Justification:
  • Picking one vertex from each triangle (clause) fulfills the requirement.

Arguments for Equivalence

• Forward Direction: If there is an independent set of size k:
  • Must contain exactly one vertex from each triangle, corresponding to a true literal, satisfying the formula.
• Reverse Direction: If there is a satisfying assignment for the formula:
  • Can construct an independent set of size k by selecting true literals from each clause's triangle.

Conclusion

• The construction shows the relationship between 3SAT and the Independent Set problem through a systematic method of graph construction and logical consistency.