ConceptTheory & Algos
NP-complete
A problem is NP-complete if it is in NP and it is NP-hard.
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
9Each in their own terms, from the easiest level.
Emily Riehl
A class of computational problems in computer science that are very hard and may not necessarily have a stable solution.Erik Demaine
Ryan O'Donnell
A class of problems that are the hardest in NP, for which no deterministic polynomial-time algorithm is known.Erik Demaine & Srini Devadas
A problem that is in NP and is at least as hard as any other problem in NP.Colva Roney-Dougal
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.David Witmer
A problem that is both in NP and at least as hard as any other problem in NP (NP-hard).Michael Sipser
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
A language S is NP-complete if it is both NP-hard and in NP.William Thurston
A class of decision problems that are both in NP and NP-hard, meaning they are among the hardest problems in NP.
Lectures that assume it
2Connections
24The lectures that define it or assume it, and the concepts next to it.