Understanding NP-Completeness and Reductions in Computer Science

Dive into the concept of NP-completeness and reductions in computer science, exploring topics such as 3SAT, E3SAT, EU3SAT, 1-in-EU3SAT, and SUBSETSUM. Learn about weak and strong NP-hardness, witness concepts, and the review of past lectures touching on NP, problems easy to verify, and more.

• NP-Completeness
• Reductions
• Computer Science
• 3SAT
• SUBSETSUM

daevo Follow

Uploaded on Sep 19, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. CS 121: Lecture 21 More NP-completeness by Reductions Adam Hesterberg https://madhu.seas.Harvard.edu/courses/Fall2020 Book: https://introtcs.org { The whole staff (faster response): CS 121 Piazza How to contact us Only the course heads (slower): cs121.fall2020.course.heads@gmail.com

2. Announcements: 121.5: Nicole Immorlica: Econ and CS Sections: Polynomial time reductions, NP, etc. Homework 5 due today. Midterm 2 this Tuesday! 90 minutes (70 if handwritten) 2-sided cheatsheet, noncollaboratively made, plus Barak s textbook. Material through lecture 17 (Efficient Computation: P)

3. Where we are: Part I: Circuits: Finite computation, quantitative study Part II: Automata: Infinite restricted computation, quantitative study Part III: Turing Machines: Infinite computation, qualitative study Part IV: Efficient Computation: Infinite computation, quantitative study Part V: Randomized computation: Extending studies to non-classical algorithms

4. Review of last lectures Reductions: ? ?? ? such that ? ? ? = ? ? ? , ? polytime. 3SAT ? ISET NP: problems easy to verify. ?: 0,1 0,1 is in NP iff: ??: 0,1 0,1 0,1 s.t. ? 0,1 , ? ? = 1 ? 0,1 such that ???,? = 1 and ???,? computable in time poly ? (Any problem in NP) ? NANDSAT ? 3NAND ? 3SAT So 3SAT is NP-Complete!

5. Witness, the NP concept Function ? is in NP if polytime ?? s.t. (? ? = 1) ( ?:???,? = 1) Verifier ?? Function F 3SAT(formula) Variable values Check: formula satisfied? Longpath(G) Sequence of vertices COMPOSITE(x) Factors p, q COMPOSITE(x) y, z Witness w Check: is path, is long Check: p*q=x Check: ?? ? ?, ? ? ?, ? ? ?

6. Witness, the computer game

7. Today: Some NP-complete problems 3SAT ? E3SAT ? EU3SAT ? 1-in-EU3SAT ? SUBSETSUM Weak NP-hardness: hard only for big-number inputs Strong NP-hardness: hard even for small-number inputs.

8. 3SAT ? E3SAT Last time, 3NAND ? 3SAT : ? ? ? ? = ????(?,?) ? ? ? ? 3SAT: Formulas like (?7 ?17 ?29) (?7 ?15 ?22) (?22 ?29), at most 3 variables/clause E3SAT: Formulas like (?7 ?17 ?29) (?7 ?15 ?22) (?22 ?29 ?22), exactly 3 variables/clause.

9. 3SAT ? E3SAT (?7 ?7 ?7) (?7) Reduction: (?7 ?17 ?7) (?7 ?17) (?7 ?17 ?29) (?7 ?17 ?29) (?7 ?7 ?7) (?7 ?17 ?7) (?7 ?17 ?29) ?7 (?7 ?17) (?7 ?17 ?29) Proof: (Sound, Complete) ?7 (?7 ?17) (?7 ?17 ?29) is satisfiable (?7 ?7 ?7) (?7 ?17 ?7) (?7 ?17 ?29) is satisfiable (?7 ?17 ?7) is satisfiable with the same variable values (?7 ?17) is satisfiable

10. 3SAT ? E3SAT (?7 ?7 ?7) (?7) Reduction: (?7 ?17 ?7) (?7 ?17) (?7 ?17 ?29) (?7 ?17 ?29) (?7 ?7 ?7) (?7 ?17 ?7) (?7 ?17 ?29) ?7 (?7 ?17) (?7 ?17 ?29) Proof: (Sound, Complete) ?7 (?7 ?17) (?7 ?17 ?29) is satisfiable (?7 ?7 ?7) (?7 ?17 ?7) (?7 ?17 ?29) is satisfiable Q: Have we proved that E3SAT is NP-complete?

11. E3SAT ? EU3SAT 3SAT: Formulas like (?7 ?17 ?29) (?7 ?15 ?22) (?22 ?29), at most 3 variables/clause E3SAT: Formulas like (?7 ?17 ?29) (?7 ?15 ?22) (?22 ?29 ?22), Exactly 3 variables/clause. EU3SAT: Formulas like (?7 ?17 ?29) (?7 ?15 ?22) (?22 ?29 ?23), exactly 3 unique variables/clause.

12. E3SAT ? EU3SAT ?7 ?17 ?7 ?7 ?7 ???? ?7 ?7 ???? ?7 ?7 ???? (?7 ?7 ????) (Wherever we have t copies of a variable in a clause, change t-1 of them and add 4(t-1) clauses.) Reduction: (?7 ?17 ?7) Proof: (Sound, Complete) EU3SAT formula with clauses like ?7 ?17 ?7 ?7 ?7 ???? ?7 ?7 ???? is satisfiable ?7 ?7 ???? (?7 ?7 ????) ? E3SAT formula with clauses like ?7 ?17 ?7 is satisfiable

14. EU3SAT ? 1-in-EU3SAT 3SAT: Formulas like (?7 ?17 ?29) (?7 ?15 ?22) (?22 ?29), at most 3 variables/clause, clause is satisfied iff at least one literal is true. E3SAT: Formulas like (?7 ?17 ?29) (?7 ?15 ?22) (?22 ?29 ?22), Exactly 3 variables/clause, clause is satisfied iff at least one literal is true. EU3SAT: Formulas like (?7 ?17 ?29) (?7 ?15 ?22) (?22 ?29 ?23), exactly 3 unique variables/clause, clause is satisfied iff at least one literal is true. 1-in-EU3SAT: Formulas like ONEOF(?7,?17,?29) ONEOF(?7,?15,?22) ONEOF(?22,?29,?23), exactly 3 unique variables/clause, clause is satisfied iff exactly one literal is true.

15. EU3SAT ? 1-in-EU3SAT ????? ?,?,? ????? ?,?,? ????? ?,?,? Reduction: (? ? ?) ????? ?,?,? ????? ?,?,? is satisfiable ????? ?,?,? ? Proof: (Sound, Complete) (? ? ?) is satisfiable

16. More SAT variants

17. Knapsack Problem: Given items with costs ?0, ?1, , ?? 1 and values ?0, ?1, , ?? 1, a budget ?, and a target value ?, choose a subset of the items with total cost at most ? and value at least ?.

18. Knapsack Problem: Given items with costs ?0, ?1, , ?? 1 and values ?0, ?1, , ?? 1, a budget ?, and a target value ?, choose a subset of the items with total cost at most ? and value at least ?. Subset Sum: Given items with costs ?0, ?1, , ?? 1 and a target value ?, choose a subset of the items with total cost exactly ?.

19. 1-in-EU3SAT ? Subset Sum Formulas like ONEOF(?7,?17,?29) ONEOF(?7,?15,?22) ONEOF(?22,?29,?23) Reduction: 1-in-EU3SAT formula m clauses (here m=3) n variables (here n=7) Given items with costs ?0, ?1, , ?? 1 and a target value ?, choose a subset of the items with total cost exactly ?. Subset Sum numbers (written in base ? + 1) 0 1 1 0 ?0 ?1 ?2 ?3 0 0 0 0 ?7: ? ?7:? ?17: ? ?17:? 1 0 0 1 0 0 0 0 ONEOF(?7,?17,?29) ONEOF(?7,?15,?22) ONEOF(?22,?29,?23) 0 1 1 0 1 0 0 0 ?2? 2 ?2? 1 0 ?23: ? ?23:? 0 0 1 1 1 0 0 0 0 0 0 t 1 1 1 1 1 1 Proof of Correctness?

20. Weak NP-hardness Subset sum: Given items with costs ?0, ?1, , ?? 1 and a target value ?, choose a subset of the items with total cost exactly ?. Some numbers (costs) in reduction were exponential in n. (Poly length!) If all inputs were polynomial in n, Subset Sum isn t NP-hard. Weakly NP-hard Strongly NP-hard : NP-hard even if all numerical inputs are polynomial- sized.

21. Traveling Salesman: Given a (directed or undirected) graph G, a distance ?? for each edge ?, and a target ?, is there a walk visiting all the vertices of G whose total distance is at most ?? Strongly NP-hard (NP-hard even if ? and every ?? is small). Hint: Reduce from Longpath: Given a (directed or undirected) graph G and a target t, is there a path visiting at least t vertices? (Paths can t revisit vertices.)

23. Summary of Lecture: 3SAT ? E3SAT ? EU3SAT ? 1-in-EU3SAT ? SUBSETSUM Weak NP-hardness: hard only for big-number inputs Strong NP-hardness: hard even for small-number inputs.