ConceptTheory & Algos
Non-deterministic Turing machine
A Turing machine that can have multiple possible next states from a given state and input symbol.
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.
Savitch's theorem2Alternation1Computing functions with a non-deterministic machine1Configuration graph construction1Cook-Levin theorem1NEXP1Non-deterministic algorithm simulation1Non-deterministic decider1Non-deterministic machine computing a function1Non-deterministic running time1Non-deterministic space1Non-deterministic time complexity1
Lecturers
2Each in their own terms, from the easiest level.
Ryan O'Donnell
A Turing machine where each step can branch into multiple possible next configurations.
Lectures that assume it
16The first 12 are shown.
- The Immerman-Szelepcsényi Theorem
- P and NP, SAT, Poly-Time Reducibility
- PSPACE-Completeness
- Reductions
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Search-to-Decision, Padding, Dichotomy Theorems
- Toda's 1st Theorem and the Permanent
- Course Introduction and Overview
- NL-Completeness and Logspace Reductions
- L and NL, NL = coNL
- Provably Intractable Problems, Oracles
- Nondeterminism
Connections
25The lectures that define it or assume it, and the concepts next to it.
Concepts7
- Turing machine
- Configuration
- Savitch's theorem
- Alternation
- Computing functions with a non-deterministic machine
- Configuration graph construction
Show 1 moreShow fewer
Lectures18
- Hierarchy Theorems
- Savitch's Theorem and NL
- The Immerman-Szelepcsényi Theorem
- P and NP, SAT, Poly-Time Reducibility
- PSPACE-Completeness
- Reductions
Show 12 moreShow fewer
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Search-to-Decision, Padding, Dichotomy Theorems
- Toda's 1st Theorem and the Permanent
- Course Introduction and Overview
- NL-Completeness and Logspace Reductions
- L and NL, NL = coNL
- Provably Intractable Problems, Oracles
- Nondeterminism
- Valiant–Vazirani Theorem, and Exact Counting (#P)
- Probabilistic Computation, BPP
- The Polynomial Time Hierarchy
- Quasilinear Cook–Levin Theorem