COEN 179 Lecture Notes - Lecture 26: Dynamic Programming, Poutine
6 Jun 2020
School
Department
Course
Professor
Document Summary
Final: greedy, dynamic programming, lower bounds, p, np, np-hard. P = class of problems whose solutions can be found in poly time. Np = class of problems whose solutions can be reorganized in poly time. 399. yin . tiger:. ms am universally considered currently, hard , Idea: to show that new problem is np-hard, we show how to use its solutions to create a solution to a known hard problem k. we write k <= h and say k reduces to h. Jl (neg n ) on uniqueness uniqueness <= smalldiff uniqueness_solver(a[1n]){ return smallest_diff_solver(a[1n])!=0); Intuitively, uniqueness is no harder than smallest_difference, so uniqueness <= smallest difference. Framework: to show that a problem h is unlikely to be in p, we reduce a known. } if h sower runs in pontine then tessmer runs in poutine. Output: true if there is a simple (no repeated vertex) path in the (v, e) with at least b edges. instances:
