Hierarchy Theorems, Relativization, and Circuit Complexity
Stub. Proving that more time or space provably buys more computational power (the time and space hierarchy theorems, and exponential-space completeness), why diagonalization alone can't resolve P vs. NP (relativization — oracles exist relative to which P = NP and others relative to which P ≠ NP), and Boolean circuit complexity as an alternative, more concrete model for measuring hardness.
Corresponds to Sipser, Chapter 9. Hierarchy theorems make precise the intuition that more resources should allow solving more problems: given strictly more time (or space), a Turing machine can decide strictly more languages — proved by a diagonalization argument that simulates and deliberately disagrees with every machine using the smaller resource bound. Relativization is a sobering limitation on that same proof technique: it shows that this specific style of diagonalization argument cannot settle P vs. NP, because there exist oracles relative to which P = NP and other oracles relative to which P ≠ NP — any proof technique that “relativizes” (still works when every machine is given the same oracle) is therefore powerless to resolve the question. Circuit complexity offers a different, more hardware-like model (Boolean circuits of AND/OR/NOT gates) for measuring a problem’s inherent difficulty, and is a major avenue for attacking P vs. NP that doesn’t obviously relativize.
Outline (TODO — flesh out each)
- Hierarchy theorems — time and space
- Exponential space completeness
- Relativization — oracles, limits of the diagonalization method
- Circuit complexity