gen-define-np-completeness-and-give-one-short-worked-example-8dc9

Define NP-completeness and give one short worked example.

# NP-Completeness ## Definition A problem is **NP-complete** if: 1. **It is in NP**: A proposed solution can be verified in polynomial time 2. **It is NP-hard**: Every problem in NP can be reduced to it in polynomial time Informally: NP-complete problems are the "hardest" problems in NP. If you could solve any one of them efficiently, you could solve all NP problems efficiently. ## Worked Example: 3-SAT **Problem**: Given a Boolean formula in CNF with 3 literals per clause, is there an assignment making it TRUE? **Instance**: (x₁ ∨ x₂ ∨ ¬x₃) ∧ (¬x₁ ∨ x₃ ∨ x₄) ∧ (¬x₂ ∨ ¬x₃ ∨ ¬x₄) **Proposed solution**: x₁=T, x₂=T, x₃=F, x₄=T **Verification** (polynomial time): - Clause 1: (T ∨ T ∨ T) = **T** ✓ - Clause 2: (F ∨ F ∨ T) = **T** ✓ - Clause 3: (F ∨ T ∨ F) = **T** ✓ All clauses satisfied → **YES, satisfiable** ✓ **Why NP-complete?** - ✓ In NP: We verified the solution in O(n) time - ✓ NP-hard: Cook-Levin theorem proved every NP problem reduces to SAT (and 3-SAT follows)