NP and NPCompleteness Bryan Pearsaul Outline Decision and Optimization Problems P and NP Polynomial-Time Reducibility NP-Hardness and NP-Completeness Examples: TSP, Circuit-SAT, Knapsack Polynomial-Time Approximation Schemes Outline Backtracking Branch-and-Bound Summary References Decision and Optimization Problems Decision Problem: computational problem with intended output of “yes” or “no”, 1 or 0 Optimization Problem: computational