Review Session for EECS 376
Topics for Today
¡ñ Complexity Classes
Copyright By PowCoder代写 加微信 powcoder
¡ñ NP-Completeness Proofs
¡ñ Reductions from Search to Decision
¡ñ Approximation Algorithms
Complexity Classes
Class P: Languages that can be efficiently decided
Class NP: Languages that can be efficiently verified
Class NP-Hard: Every language in NP can be polynomial time reduced to the language
Class NP-Complete: Languages that are in NP-Hard and in NP
Search Problems
¡ñ Decision problems give ¡°yes¡± or ¡°no¡± answers
¡ñ Search problems require something like a set of integers,
a set of vertices in a graph, etc.
¡ñ Search to Decision Reduction: Suppose there is a
black-box decider. Use the decider to solve the search problem.
Practice Exam 2 Problem 30
Practice Exam 2 Problem 31
Search to Decision Reduction Problems General Strategy
¡ñ Usually involve some sort of k (edges, vertices, etc.)
¡ñ Use the decider to find the appropriate k first
¡ñ Try removing each item and see if decider would accept or
¡ñ According to the decider¡¯s behavior, determine if the item
should be in the final set returned
Approximation Algorithms
Practice Exam 1 Problem 5
Practice Exam 1 Problem 5
Practice Exam 1 Problem 5
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com