Complexity Theory Trivia Questions
- ❓ 132+ questions
- 🗂️ Mathematics
- 🎚️ Easy to expert
- ✨ Free to play
Study of computational problem difficulty. Play Complexity Theory trivia solo to sharpen your knowledge, or challenge a friend head-to-head in Trivia Tango — every question comes with an explanation so you learn as you play. Questions span every level, from easy warm-ups to expert-level stumpers, so there's a real challenge here however much you already know.
Already playing?
Sample Complexity Theory Quiz Questions
A mix of easy, medium and hard — questions run from warm-up to expert, so there's a real challenge at every level. Think you know the answers? Play to find out.
Written as a capital letter with parentheses like O(n²), this mathematical shorthand describes how an algorithm's runtime scales with input size.
Difficulty: Easy- Big O notation
- Lambda calculus
- Set-builder notation
- Sigma notation
This complexity class contains problems decidable in polynomial time by a randomized algorithm with bounded two-sided error.
Difficulty: Medium- RP
- ZPP
- BPP
- PP
Aaronson and Wigderson's algebrization barrier shows that proofs using low-degree extensions cannot separate this fundamental pair of complexity classes.
Difficulty: Hard- L and P
- P and NP
- BPP and NEXP
- PSPACE and EXP
An algorithm that runs in the same amount of time regardless of input size is said to have this type of time behavior.
Difficulty: Easy- Linear time
- Constant time
- Quadratic time
- Logarithmic time
The disjoint-set data structure achieves nearly constant time operations through path compression and this technique that keeps trees shallow.
Difficulty: Medium- Union by rank
- Tree rotation
- Lazy deletion
- Splay operations
This famous 1979 result by Furst, Saxe, and Sipser showed that XOR cannot be computed by constant-depth circuits with polynomial size.
Difficulty: Hard- Majority lower bound
- Clique lower bound
- Parity lower bound against AC⁰
- Permanent lower bound
When an algorithm's runtime doubles each time you add one more element to the input, it exhibits this explosive scaling behavior.
Difficulty: Easy- Polynomial growth
- Linear growth
- Exponential growth
- Logarithmic growth
Savitch's theorem proves that nondeterministic space can be simulated deterministically with only this modest overhead in space usage.
Difficulty: Medium- Linear increase
- Quadratic increase
- Exponential increase
- Logarithmic increase
Think You Know Complexity Theory?
Play a free round in your browser, learn something new with every answer, and challenge your friends to beat your score.
Or get the app