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

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

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**

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)

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**

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**

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)

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**

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**

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**

Social & Everyday Systems

• Scheduling and seating arrangements**
• Matching problems** (with constraints)
• Genealogy and network analysis**
• Possible shuffles of a deck**: 52! ≈ 8×1067

Why These Explode

Three recurring patterns drive the growth:

• Exponential**: kn (keys, SAT, sequences)
• Factorial**: n! (permutations, TSP, orderings)
• Super-exponential**: nn or 2(2n) (Boolean functions, graph structures)

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)