Non-determinism
One word, taught differently in 2 fields. Each use is given apart.
In Theory & Algos
A computational model where the machine can be in multiple states or follow multiple paths simultaneously, accepting if at least one path reaches an accept state.
In Systems & CS
The behavior where running the same prompt and task yields different code output even at temperature zero.
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.
In Theory & Algos
1Michael Sipser
In Systems & CS
1Lectures that assume it
7Connections
17The lectures that define it or assume it, and the concepts next to it.
Lectures11
- P and NP, SAT, Poly-Time Reducibility
- Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
- Probabilistic Computation, BPP
- Java for Agentic Development: A Case for Stability and Robustness
- Complexity: P, NP, NP-completeness, Reductions
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class