Advanced Computation and Complexity Concepts
Advanced concepts
Regular expressions
Describe exactly the regular languages — equivalent in expressive power to DFAs/NFAs. Kleene's theorem establishes the equivalence; the choice between them is convenience, not capability.
NP-hard
At least as hard as every problem in NP, but not necessarily in NP itself. Need not be decidable or verifiable in polynomial time — distinct from NP-complete, which must also be in NP.
Proving NP-completeness
Show the new problem is in NP, then reduce a known NP-complete problem to it in polynomial time. Both steps are required — membership alone or hardness alone is insufficient.
PSPACE
Problems solvable using polynomial space, with no time bound. NP ⊆ PSPACE; PSPACE is not a subset of NP. Space can be reused, so PSPACE is broad.
Linear bounded automaton
A Turing machine restricted to tape proportional to input length. Recognizes context-sensitive languages — between context-free and recursively enumerable.
Approximation algorithms
Used for NP-hard optimization problems where exact solutions are infeasible. Trade optimality for tractable runtime; the approximation ratio bounds how far the result can be from optimal.
Monte Carlo vs Las Vegas
Monte Carlo runs in bounded time but may return an incorrect answer with some probability. Las Vegas always returns a correct answer but has variable (randomized) runtime. The trade is correctness vs time guarantee.
Probabilistic classes
RP, BPP, ZPP classify problems by randomized algorithms with bounded error. BPP allows two-sided error; ZPP corresponds to Las Vegas. P ⊆ BPP is known; BPP vs P is open.
One-way functions
Easy to compute, computationally infeasible to invert. The foundation of modern cryptography — their existence implies P ≠ NP, though existence is unproven.
Omega-automata
Automata over infinite-length inputs (e.g., Büchi automata). Needed to model and verify nonterminating systems such as servers and reactive controllers, where execution traces never end.
Pumping lemma
Formal tool to prove a language is not regular (or not context-free) by showing no valid pumping decomposition exists. A proof technique, not a recognizer.
CFG derivations
A production like A → aA | b generates strings of the form a*b — recursion on the variable yields unbounded repetition terminating in the base case.
Watch out for
  • NP-hard is not the same as NP-complete — NP-hard need not be in NP and need not be decidable.
  • All context-free languages are NOT regular — nesting requires a stack beyond finite-state power.
  • PSPACE ⊆ NP is false in general; the known direction is NP ⊆ PSPACE.
  • Monte Carlo trades correctness for fixed runtime; Las Vegas trades runtime for guaranteed correctness — do not swap them.
  • Use the pumping lemma to prove non-regularity, not a DFA — you cannot prove absence of a DFA by building one.
  • Optimizing an NP problem's verification speed is not the same as solving it faster — verification is the NP defining property.
→ This page was created with help from Claude AI.