Algorithms for NP-Hard Problems (Section 19.6: Rookie Mistakes)

preview_player
Показать описание
NP-hardness is a pretty technical topic but at the same time highly relevant for practicing algorithm designers and serious programmers. Outside of textbooks and research papers, liberties are often taken with the precise mathematical definitions in the interest of easier communication. Some types of inaccuracies will mark you as a clueless newbie, while others are culturally acceptable. How would you ever know which is which? Because I’m going to tell you, right now.
  1. Tim Roughgarden Lectures
Рекомендации по теме
Algorithms for NP-Hard 0:10:05

Algorithms for NP-Hard Problems (Section 19.0: Overview and Prerequisites)

Algorithms for NP-Hard 0:16:19

Algorithms for NP-Hard Problems (Section 19.1: The Algorithmic Mystery of MST vs. TSP)

Algorithms for NP-Hard 0:07:37

Algorithms for NP-Hard Problems (Section 23.2: Decision, Search, and Optimization)

Algorithms for NP-Hard 0:12:45

Algorithms for NP-Hard Problems (Section 20.4: The 2-OPT Heuristic for the TSP) [Part 1 of 2]

Algorithms for NP-Hard 0:26:25

Algorithms for NP-Hard Problems (Section 22.5: Directed Hamiltonian Path Is NP-Hard)

Algorithms for NP-Hard 0:24:58

Algorithms for NP-Hard Problems (Section 23.3: NP: Problems with Easily Recognized Solutions)

8. NP-Hard and 0:31:53

8. NP-Hard and NP-Complete Problems

Algorithm for NP-Hard 0:26:07

Algorithm for NP-Hard Problems (Section 19.5: A Simple Recipe for Proving NP-Hardness)

Algorithms for NP-Hard 0:20:10

Algorithms for NP-Hard Problems (Section 20.2: A Greedy Heuristic for Maximum Coverage) [Part 1/2]

Algorithms for NP-Hard 0:09:23

Algorithms for NP-Hard Problems (Section 22.1: Reductions Revisited)

Algorithms for NP-Hard 0:25:07

Algorithms for NP-Hard Problems (Section 22.3: The Big Picture)

Algorithms for NP-Hard 0:09:53

Algorithms for NP-Hard Problems (Section 19.6: Rookie Mistakes)

Algorithms for NP-Hard 0:24:40

Algorithms for NP-Hard Problems (Section 19.4: Algorithmic Strategies for NP-Hard Problems)

Algorithms for NP-Hard 0:23:12

Algorithms for NP-Hard Problems (Section 20.5: Principles of Local Search) [Part 1 of 2]

Algorithms for NP-Hard 0:06:12

Algorithms for NP-Hard Problems (Section 24.5: The Final Outcome)

Algorithms for NP-Hard 0:12:05

Algorithms for NP-Hard Problems (Section 23.4: The P!=NP Conjecture)

Algorithms for NP-Hard 0:19:18

Algorithms for NP-Hard Problems (Section 23.6: NP-Completeness)

Algorithms for NP-Hard 0:19:35

Algorithms for NP-Hard Problems (Section 21.1: The Bellman-Held-Karp Algorithm for TSP) [Part 1/2]

Algorithms for NP-Hard 0:18:46

Algorithms for NP-Hard Problems (Section 23.5: The Exponential Time Hypothesis)

Algorithms for NP-Hard 0:17:19

Algorithms for NP-Hard Problems (Section 24.3: Feasibility Checking) [Pt 1/2]

Algorithms for NP-Hard 0:11:12

Algorithms for NP-Hard Problems (Section 23.1: Amassing Evidence of Intractability)

Algorithms for NP-Hard 0:08:24

Algorithms for NP-Hard Problems (Section 21.3: Problem-Specific Algorithms vs. Magic Boxes)

Algorithms for NP-Hard 0:11:58

Algorithms for NP-Hard Problems (Section 20.4: The 2-OPT Heuristic for the TSP) [Part 2/2]

Algorithms for NP-Hard 0:24:27

Algorithms for NP-Hard Problems (Section 21.5: Satisfiability Solvers)

Комментарии
Автор

Assuming P =/= NP helps me make sure I'm doing the reduction in the right direction. "Let's assume I have a P-time algorithm for 3COLOR. I could use it to solve SAT. But (loosely speaking) SAT can't be solved in P-time. So there's a contradiction in my assumption. QED."

Bunnokazooie