Sign inSign in

NP-complete

A problem is NP-complete if it is in NP and it is NP-hard.
as Erik Demaine defines itMITThe wording closest to all 12 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Opens up

Concepts that name this one as a prerequisite.

Lecturers

9

Each in their own terms, from the easiest level.

  • Emily Riehl

    Perimeter Institute · Introductory

    A class of computational problems in computer science that are very hard and may not necessarily have a stable solution.
    • 42:38A Solution to the Stable Marriage Problem
  • Erik Demaine

    MIT · Undergraduate

    • 37:39Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
    • 37:52Computational Complexity
  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    A class of problems that are the hardest in NP, for which no deterministic polynomial-time algorithm is known.
    • 45:02The Complexity Class coNP
    • 40:00Rotate, Compute, Rotate
  • Erik Demaine & Srini Devadas

    MIT · Undergraduate

    A problem that is in NP and is at least as hard as any other problem in NP.
    • 14:25Course Overview, Interval Scheduling
  • Colva Roney-Dougal

    Gresham College · Undergraduate

    A problem is NP-complete if it is in NP and a polynomial time solution to it implies that every problem in NP can be solved in polynomial time.
    • 28:32How Hard is too Hard? An Introduction to Complexity
  • David Witmer

    Carnegie Mellon University · Undergraduate

    A problem that is both in NP and at least as hard as any other problem in NP (NP-hard).
    • 2:20NP-Completeness Reductions
  • Michael Sipser

    MIT · Undergraduate

    A language B is NP-complete if B is in NP and for all A in NP, A is polynomial time reducible to B.
  • Yu Zhao

    Carnegie Mellon University · Undergraduate

    A language S is NP-complete if it is both NP-hard and in NP.
    • 15:40NP-Completeness and the Cook-Levin Theorem
  • William Thurston

    Clay Mathematics Institute · Graduate

    A class of decision problems that are both in NP and NP-hard, meaning they are among the hardest problems in NP.
    • 40:42The Mystery of 3-Manifolds

Lectures that assume it

2

Connections

24

The lectures that define it or assume it, and the concepts next to it.

Concepts10

Show 4 more

Lectures14

Show 8 more

9 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.