ECE 595E Lecture 4: NP-hardness

By Peter Bermel

Electrical and Computer Engineering, Purdue University, West Lafayette, IN

View Presentation

Additional materials available (4)

Category

Online Presentations

Published on

Abstract

Outline:

  • Recap from Friday
  • Class NP
  • Non-deterministic Turing machines
  • Reducibility
  • Cook-Levin theorem
  • Coping with NP Hardness

Cite this work

Researchers should cite this work as follows:

  • Peter Bermel (2013), "ECE 595E Lecture 4: NP-hardness," https://nanohub.org/resources/16572.

    BibTex | EndNote

Time

Location

EE 226, Purdue University, West Lafayette, IN

Tags

  1. course lecture
  2. Programming
  3. Simulation
ECE 595E Lecture 4: NP-hardness
  • Lecture 4: NP-hardness 1. Lecture 4: NP-hardness 0
    00:00/00:00
  • Outline 2. Outline 67.13380046713381
    00:00/00:00
  • Recap from Friday 3. Recap from Friday 150.78411745078412
    00:00/00:00
  • Examples in P 4. Examples in P 376.77677677677679
    00:00/00:00
  • Class NP Definition 5. Class NP Definition 557.92459125792459
    00:00/00:00
  • Examples of NP 6. Examples of NP 631.9319319319319
    00:00/00:00
  • Relationship of P & NP 7. Relationship of P & NP 1156.0560560560562
    00:00/00:00
  • Relationship of P & NP 8. Relationship of P & NP 1211.0443777110445
    00:00/00:00
  • Relationship of P & NP 9. Relationship of P & NP 1336.1361361361362
    00:00/00:00
  • Non-deterministic Turing machines 10. Non-deterministic Turing machi… 1388.3883883883884
    00:00/00:00
  • Reducibility 11. Reducibility 1500.9342676009344
    00:00/00:00
  • NP completeness 12. NP completeness 1739.4060727394062
    00:00/00:00
  • Cook-Levin theorem 13. Cook-Levin theorem 1823.2565899232566
    00:00/00:00
  • Web of reductions 14. Web of reductions 2138.2716049382716
    00:00/00:00
  • Coping with NP-hardness 15. Coping with NP-hardness 2265.5321988655323
    00:00/00:00
  • Related Complexity Classes 16. Related Complexity Classes 2503.2365699032366
    00:00/00:00
  • What if P=NP? 17. What if P=NP? 2606.1061061061064
    00:00/00:00
  • Next Class 18. Next Class 2812.2455789122455
    00:00/00:00
Pop Out