Oracle
One word, taught differently in 3 fields. Each use is given apart.
In Theory & Algos
A black box that can answer membership queries for a specific language in a single step.
In Systems & CS
A tool that can answer a very simple question: where does this piece of code come from?
In Engineering
An abstraction for a solver that can answer yes or no to whether a polynomial is positive for all x.
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.
Complexity class1Firmware analysis1Language1Polynomial positivity1Reverse engineering1Sum of squares optimization1Turing machine1
Opens up
Concepts that name this one as a prerequisite.
In Theory & Algos
1In Systems & CS
1In Engineering
1Lectures that assume it
9- Hardness within P
- Toda's 1st Theorem and the Permanent
- Instance Checking and the Permanent
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies
- Quantum Algorithms Synthesis I: The Hadamard Transform
- Valiant–Vazirani Theorem, and Exact Counting (#P)
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- More on constant-round interactive proof systems
Connections
19The lectures that define it or assume it, and the concepts next to it.
Concepts7
- Language
- Reverse engineering
- Relativization
- $\Sigma_2^P$
- Binary search on counting complexity
- Downward self-reducibility
Show 1 moreShow fewer
Lectures12
- Provably Intractable Problems, Oracles
- Computing Lyapunov Functions II
- Hash All The Things / Get All The Sig(s): Automatic Function Detection for Reverse Engineers
- Hardness within P
- Toda's 1st Theorem and the Permanent
- Instance Checking and the Permanent
Show 6 moreShow fewer
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies
- Quantum Algorithms Synthesis I: The Hadamard Transform
- Valiant–Vazirani Theorem, and Exact Counting (#P)
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- More on constant-round interactive proof systems