Theory of Computation Practice (Interactive)
University Computing, Theory of Computation Practice
10 auto-graded practice problems at medium to hard difficulty. Select an answer, submit, and review the explanation.
Automata and Regular Languages
Context-Free Grammars and Turing Machines
Complexity Classes
Common Mistakes
Confusing decidable with decidable in polynomial time: Decidable means a Turing machine can solve it (halts on all inputs). Polynomial time means it can be solved efficiently. Some problems are decidable but require exponential time.
Forgetting that NP includes P: P ⊆ NP. All problems solvable in polynomial time are also verifiable in polynomial time. Don’t assume NP problems are always hard.
Mixing up reduction with simulation: Reduction transforms one problem into another. Simulation runs one machine on another’s input. They’re different concepts in computability theory.