ECE 695NS Lecture 2: Computability and NP-hardness

By Peter Bermel

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

Published on

Abstract

Outline:

  • Overview
  • Definitions
  • Computing Machines
  • Church-Turing Thesis
  • Polynomial Time (Class P)
  • 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 (2017), "ECE 695NS Lecture 2: Computability and NP-hardness," http://nanohub.org/resources/25676.

    BibTex | EndNote

Time

Location

EE 317, Purdue University, West Lafayette, IN

Tags