Cryptography & Security

- **Symmetric key search**: AES-128 has 2128 ≈ 3.4×1038 keys; AES-256 has ≈ 1.2×1077

- **Asymmetric keys**: RSA-2048 factoring space, elliptic curve discrete log (~2256)

- **Password and passphrase spaces**: grow as (alphabet size)length

- **Hash preimage and collision search**: SHA-256 preimage ≈ 2256

- **Side-channel and fault-injection key-recovery spaces**

- **Lattice problems** (post-quantum): shortest vector search in high dimensions

1. Games & Puzzles

- **Chess**: ~1044 positions, game tree ~10120 (Shannon number)

- **Go (19×19)**: ~2×10170 legal positions

- **Shogi, Xiangqi, Arimaa, Stratego**: 1071 to 10535 game-tree complexity

- **Rubik's Cube**: 4.3×1019 states (larger cubes: 7×7×7 ≈ 10160)

- **Sudoku/Latin squares**: ~6.7×1021 valid 9×9 grids

- **Poker (Texas Hold'em)**: ~10161 decision points in no-limit

- **Sliding-tile puzzles**: 24-puzzle ≈ 7.8×1024; 35-puzzle ≈ 1041

1. Optimization & Operations Research

- **Traveling Salesman Problem**: (n-1)!/2 tours; 60 cities ≈ 1080

- **Vehicle routing, job-shop and flow-shop scheduling**

- **Knapsack, bin packing, set cover, graph coloring**

- **Quadratic assignment problem** (facility layout)

- **Timetabling** (exams, courses, airline crew pairing)

- **Integer programming** (branching trees)

- **Network design and facility location**

1. Logic, Computation & Verification

- **Boolean satisfiability (SAT)**: 2n assignments for n variables

- **Constraint satisfaction problems**

- **Model checking**: state-space explosion in concurrent systems (interleavings of threads)

- **Program analysis and symbolic execution**: path explosion from branching

- **Software and hardware testing**: input-combination spaces, feature-interaction bugs

- **Theorem proving and automated planning**: proof/plan search trees

- **Circuit design verification** (Boolean function spaces: 2(2n) functions of n inputs)

1. Biology & Chemistry

- **Protein folding** (Levinthal's paradox): ~10143 conformations for a 100-residue chain

- **Protein sequence space**: 20n sequences (a 100-residue protein ≈ 10130)

- **DNA/RNA sequences**: 4n (a human genome ≈ 4(3×109))

- **Chemical space**: ~1060 drug-like molecules

- **Molecular docking and conformer search**

- **Gene regulatory networks and epistasis**: combinations of mutations

- **Phylogenetic tree inference**: (2n-5)!! trees (50 species ≈ 1076)

- **Multiple sequence alignment**

1. Physics & Materials Science

- **Quantum many-body systems**: Hilbert space dimension 2n (exponential in particles)

- **Ising and spin-glass models**: 2N configurations

- **Crystal structure prediction** and alloy composition search

- **Lattice gauge theory configurations**

- **Statistical mechanics partition functions**

1. Artificial Intelligence & Machine Learning

- **Neural architecture search** and hyperparameter combinations

- **Feature subset selection**: 2n subsets

- **Reinforcement learning state spaces** (e.g., Atari pixels, robotics)

- **Bayesian network structure learning**: super-exponential in nodes

- **Natural language**: possible sentences from a vocabulary V of length L is VL

- **Image space**: 256(w×h×3) possible images

- **Combinatorial action spaces** in strategy games (StarCraft ≈ 1026 actions per step)

1. Mathematics

- **Graph enumeration**: number of labeled graphs on n vertices is 2(n(n-1)/2)

- **Permutations and partitions**: n! and Bell numbers

- **Ramsey numbers** and extremal combinatorics

- **Latin squares, block designs, error-correcting code search**

- **Boolean function and cellular automata rule spaces**

- **Collatz-like and Busy Beaver searches**

1. Engineering & Industry

- **Chip layout/placement and routing**: ~102500 placements for modern chips

- **Configuration management** (product variants, option combinations)

- **Supply chain and logistics planning**

- **Power-grid unit commitment**

- **Telecom network routing and spectrum allocation**

- **Satellite constellation scheduling**

- **Architectural and mechanical design spaces**

1. Finance & Economics

- **Portfolio optimization** with discrete constraints

- **Combinatorial auctions**: 2n bundles for n items

- **Option and derivative path-dependency**

- **Market microstructure and agent-based simulations**

1. Social & Everyday Systems

- **Scheduling and seating arrangements**

- **Matching problems** (with constraints)

- **Genealogy and network analysis**

- **Possible shuffles of a deck**: 52! ≈ 8×1067

1. Why These Explode

Three recurring patterns drive the growth:

1. **Exponential**: kn (keys, SAT, sequences)

2. **Factorial**: n! (permutations, TSP, orderings)

3. **Super-exponential**: nn or 2(2n) (Boolean functions, graph structures)

1. Common Resolution Strategies

Since brute force fails at these scales, the field relies on:

- **Pruning**: branch-and-bound, alpha-beta, constraint propagation

- **Heuristics/metaheuristics**: simulated annealing, genetic algorithms, tabu search

- **Learned guidance**: Monte Carlo tree search, neural-guided search (AlphaGo, AlphaFold)

- **Decomposition**: dynamic programming, divide-and-conquer, symmetry reduction

- **Relaxation and approximation**: LP relaxation, approximation algorithms

- **Probabilistic methods**: sampling, SAT solvers with clause learning (CDCL)

- **Structure exploitation**: algebraic attacks, meet-in-the-middle, number-field sieve

- **Quantum algorithms**: Grover (square-root speedup), Shor (factoring)

If you'd like, I can go deeper on any one domain, or put this into a table or document with the state-space sizes and the best-known resolution method for each.