Systems That Exhibit Combinatorial Explosion

New name   B I U S link image code HTML list	Show page  Syntax
Here are the main domains, grouped by field, with typical scale where it's meaningful. !!Cryptography & Security * Symmetric key search**: AES-128 has 2^128 ≈ 3.4×10^38 keys; AES-256 has ≈ 1.2×10^77 * Asymmetric keys**: RSA-2048 factoring space, elliptic curve discrete log (~2^256) * Password and passphrase spaces**: grow as (alphabet size)^length * Hash preimage and collision search**: SHA-256 preimage ≈ 2^256 * Side-channel and fault-injection key-recovery spaces** * Lattice problems** (post-quantum): shortest vector search in high dimensions !!Games & Puzzles * Chess**: ~10^44 positions, game tree ~10^120 (Shannon number) * Go (19×19)**: ~2×10^170 legal positions * Shogi, Xiangqi, Arimaa, Stratego**: 10^71 to 10^535 game-tree complexity * Rubik's Cube**: 4.3×10^19 states (larger cubes: 7×7×7 ≈ 10^160) * Sudoku/Latin squares**: ~6.7×10^21 valid 9×9 grids * Poker (Texas Hold'em)**: ~10^161 decision points in no-limit * Sliding-tile puzzles**: 24-puzzle ≈ 7.8×10^24; 35-puzzle ≈ 10^41 !!Optimization & Operations Research * Traveling Salesman Problem**: (n-1)!/2 tours; 60 cities ≈ 10^80 * 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)**: 2^n 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^(2^n) functions of n inputs) !!Biology & Chemistry * Protein folding** (Levinthal's paradox): ~10^143 conformations for a 100-residue chain * Protein sequence space**: 20^n sequences (a 100-residue protein ≈ 10^130) * DNA/RNA sequences**: 4^n (a human genome ≈ 4^(3×10^9)) * Chemical space**: ~10^60 drug-like molecules * Molecular docking and conformer search** * Gene regulatory networks and epistasis**: combinations of mutations * Phylogenetic tree inference**: (2n-5)!! trees (50 species ≈ 10^76) * Multiple sequence alignment** !!Physics & Materials Science * Quantum many-body systems**: Hilbert space dimension 2^n (exponential in particles) * Ising and spin-glass models**: 2^N 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**: 2^n 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 V^L * Image space**: 256^(w×h×3) possible images * Combinatorial action spaces** in strategy games (StarCraft ≈ 10^26 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**: ~10^2500 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**: 2^n 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×10^67 !!Why These Explode Three recurring patterns drive the growth: * Exponential**: k^n (keys, SAT, sequences) * Factorial**: n! (permutations, TSP, orderings) * Super-exponential**: n^n or 2^(2^n) (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)
Password  Summary of changes

 📜 ⏱️ ⬆️