Mathematics and Logic

Computational Complexity is the branch of theoretical computer science that classifies algorithms and computational problems according to their inherent difficulty, measuring the asymptotic scaling of required resources—primarily time (execution steps), space (memory), and data (sample complexity)—as the size of the input grows. In Artificial Intelligence, complexity theory strictly bounds what is theoretically computable and practically tractable, differentiating problems that scale gracefully (polynomial time) from those that suffer combinatorial explosion (exponential time), thereby defining the fundamental physical limits of machine reasoning and model scaling (Arora & Barak, 2009).

An algorithm is mathematically useless if evaluating it requires more time than the lifespan of the universe or more memory than atoms in the earth. The significance of computational complexity in AI lies in understanding that scaling hardware alone cannot overcome fundamentally intractable algorithms.

Key implications for AI include:

1. Algorithmic Tractability: Classical Symbolic AI repeatedly failed because exact logical deduction and planning in open domains are NP-hard (or undecidable); scaling hardware by a factor of 1,000 provides almost zero benefit against an exponential scaling curve.
2. Deep Learning Viability: The success of modern deep learning stems from transforming discrete, NP-hard combinatorial problems into continuous, differentiable optimization problems where approximate solutions can be found in polynomial time using highly parallelized GPUs.
3. The Inference Bottleneck: In modern architectures like Transformers, complexity determines the economic viability of deployment (e.g., the quadratic $O(N^2)$ time complexity of self-attention).

Computational complexity theory emerged in the 1960s (Hartmanis & Stearns, 1965). Stephen Cook (1971) introduced NP-completeness via Boolean satisfiability, and Richard Karp (1972) showed that many combinatorial problems, including the travelling salesperson decision problem, are NP-complete.

During the first AI Winter, researchers collided with the reality of exponential complexity. The Lighthill Report (1973) is generally associated with the critique that combinatorial explosion limited classical AI search techniques to simplified "toy" environments [VERIFICATION NEEDED: report text not accessed; whether it names combinatorial explosion as the primary reason].

In the late 20th century, Valiant (1984) bridged complexity and machine learning through Probably Approximately Correct (PAC) learning, quantifying the sample complexity—how much data is required to guarantee learning a concept within a specified error margin in polynomial time. Today, complexity research in AI focuses heavily on the asymptotic scaling of deep learning architectures, prompting the development of sparse and linear-time approximations to circumvent quadratic bottlenecks.

#4.1 Asymptotic Analysis and Big-O Notation

Big-O notation describes the upper bound of an algorithm's growth rate as the input size $N$ approaches infinity:

• $O(1)$ (Constant): Hash table lookups (expected time).
• $O(N)$ (Linear): Scanning a dataset; ideal for linear-time state-space models.
• $O(N \log N)$ (Log-linear): Efficient sorting; Fast Fourier Transforms.
• $O(N^2)$ (Quadratic): Pairwise comparison of all items; standard Transformer self-attention over sequence length $N$.
• $O(N^3)$ (Cubic): Naive multiplication of two $N \times N$ matrices.
• $O(2^N)$ (Exponential): Brute-force search over boolean variables.

#4.2 The Classes P, NP, and NP-Hard

• P (Polynomial Time): Problems that can be solved by a deterministic Turing machine in polynomial time. (Tractable).
• NP (Nondeterministic Polynomial Time): Decision problems for which a proposed solution can be verified in polynomial time.
• NP-Hard: Problems that are at least as hard as the hardest problems in NP.
• NP-Complete: Problems that are both in NP and NP-Hard.

While it is widely suspected by computer scientists that $\text{P} \neq \text{NP}$, this remains unproven. However, just because a problem class is worst-case NP-hard does not mean that specific, real-world instances cannot be solved efficiently using heuristics and approximation algorithms.

#4.3 Neural Network Complexity (Transformers)

The computational cost of a standard Transformer is dominated by two components:

1. Self-Attention: Computing the matrix product $Q K^\top$ requires $O(N^2 \cdot d)$ time and $O(N^2)$ space, where $N$ is sequence length and $d$ is embedding dimension. This quadratic bottleneck prevents infinite context windows.
2. Feed-Forward Networks (FFN): Requires $O(N \cdot d^2)$ time. As models grow wider (larger $d$), the FFN dominates the FLOP count for short sequences.

During autoregressive decoding (inference), the model generates one token at a time. The attention mechanism requires reading the KV Cache (past Keys and Values) from GPU memory. The memory bandwidth required to load the KV cache for every token scales as $O(N \cdot d)$, severely bottlenecking generation speed (Shazeer, 2019).

In AI, complexity is measured across multiple orthogonal dimensions:

• Time Complexity: Number of basic operations (FLOPs) required to compute a forward or backward pass.
• Space Complexity: VRAM required to store model parameters, gradients, and optimizer states.
• Sample Complexity: The number of training examples required to bound the generalization error (critical in statistical learning theory).
• Communication Complexity: The volume of data that must be passed between GPU nodes in a distributed training cluster (bottlenecked by interconnects like NVLink or InfiniBand).

• Approximation: Because exact probabilistic inference in Bayesian belief networks is NP-hard in general (Cooper, 1990), researchers use Variational Inference or Markov Chain Monte Carlo (MCMC) to approximate the distribution in polynomial time.
• Pruning and Sparsity: Mixture-of-Experts (MoE) architectures decouple parameter count from time complexity. For example, the Mixtral 8x7B paper reports that each token has access to 47B parameters but uses 13B active parameters during inference (Jiang et al., 2024); per-token compute scales with active, not total, parameters.
• Quantization: Reducing the precision of model weights from 16-bit floats (FP16) to 4-bit integers (INT4) reduces memory footprint and memory-bandwidth requirements roughly in proportion to the bit width; the accompanying accuracy degradation is an empirical question that varies by model and method [VERIFICATION NEEDED: source for quantization trade-offs].

#Limits of Complexity Theory

Worst-case asymptotic analysis is often overly pessimistic for machine learning.

1. Average-Case vs. Worst-Case: Many AI problems are NP-hard in the worst case (e.g., training a 3-node neural network is NP-complete in a specific formulation; Blum & Rivest, 1992), but highly tractable in the average case over real-world data distributions.
2. Hidden Constants: Big-O ignores constant factors. An $O(N)$ algorithm with a massive constant overhead may be slower in practice than an $O(N^2)$ algorithm for all practical input sizes.

#Unresolved Scientific Questions

1. P vs. NP: The millennium prize problem. If $\text{P} = \text{NP}$, all NP problems can be solved in polynomial time, radically transforming AI planning, theorem proving, and cryptography.
2. Sub-Quadratic Attention: Can linear-time architectures ($O(N)$) like Mamba (Gu & Dao, 2023) or RWKV (Peng et al., 2023) match the expressive power and in-context recall capabilities of $O(N^2)$ exact softmax attention across scaling laws?

Current AI engineering treats computational complexity as an economic ceiling. Training FLOPs can be estimated from parameter and token counts, and scaling laws (Kaplan et al., 2020) predict loss as a function of those inputs. To circumvent quadratic attention costs, the field utilizes techniques like FlashAttention (Dao et al., 2022), which computes exact attention using hardware-aware tiling to reduce memory traffic [VERIFICATION NEEDED: the paper's stated memory bound, taken here as $O(N)$ extra memory with $O(N^2)$ time], and Grouped-Query Attention (Ainslie et al., 2023), which reduces the size of the KV cache.

The following are plausible scenarios, not established facts, each registered as a forecast record.

• Near-Term (0–3 Years): Plausible emphasis on inference optimization, including speculative decoding (Leviathan et al., 2023), continuous batching and low-rank adaptation (LoRA; Hu et al., 2021) (FCST-FOUND-004-001).
• Medium-Term (3–10 Years): Plausible hardware-algorithm co-design that minimizes data movement as well as FLOPs (FCST-FOUND-004-002).
• Long-Term (10+ Years): Speculative search for architectures that decouple reasoning depth from sequence length (FCST-FOUND-004-003). The earlier phrasing of "$O(1)$ inference scaling" is not a defined target and is omitted.

• Foundational Concepts:
  • FOUND-001 Artificial Intelligence: The overarching discipline.
• Related Methods & Technologies:
  • TECH-ARCH-001 The Transformer Architecture: The primary subject of modern complexity bottlenecks.
  • TECH-LLM-001 Large Language Models: Training and inference constraints.
• Advanced Implications & Future Trajectories:
  • ECON-COMP-001 The Economics of Compute & Scaling: How theoretical complexity translates directly into capital expenditure.
  • AGI-PATH-001 Scientific Pathways to AGI: The role of test-time compute vs. fast inference.

Probability theory is the mathematical framework for quantifying uncertainty; statistics is the discipline of drawing conclusions about populations or processes from finite data; and Bayesian inference is the approach to statistics in which beliefs about unknown quantities are expressed as probability distributions and revised by conditioning on evidence using Bayes' theorem. These three form the mathematical basis of most modern machine learning, in which models are trained by maximizing likelihoods, evaluated by estimating expected error, and increasingly asked to report calibrated uncertainty.

AI systems operate with incomplete, noisy and ambiguous information. A language model must choose among continuations, a medical classifier must decide on partial symptoms, and a robot must act on noisy sensor readings. Probability provides a consistent calculus for these situations. In the 1980s, probabilistic methods displaced much of the rule-based treatment of uncertainty in AI, and Pearl's (1988) work on probabilistic reasoning in graphical models is a central reference for that shift.

Three roles of probability in AI should be distinguished.

1. As a modelling language. Generative and discriminative models define distributions over data (for example, a language model defines $p(x_t \mid x_{<t})$).
2. As an estimation framework. Parameters are fit by maximum likelihood or Bayesian posteriors; common loss functions such as cross-entropy and squared error correspond to negative log-likelihoods under particular noise assumptions.
3. As a normative standard for decisions under uncertainty. Combined with utilities, probability yields expected-utility maximization (FOUND-012 Game Theory and Decision Theory).

The significance of the Bayesian view is both practical and conceptual. Practically, it supplies a principled route to uncertainty quantification and regularization. Conceptually, it is a candidate account of rational belief revision, which connects to the foundations of intelligence (FOUND-002 Definitions of Intelligence). That conceptual claim is philosophical and is not accepted by all statisticians (Section 7).

Bayes's essay on the doctrine of chances, published posthumously in 1763, solved a problem of inverse probability: inferring the chance of an event from observed frequencies (Bayes, 1763). The general method was later developed in other hands; this article does not attempt to attribute priority for the full theorem.

Through the twentieth century, frequentist methods (significance tests, confidence intervals, maximum likelihood) dominated applied statistics, while Bayesian methods were developed by a smaller community, notably in the physical sciences (Jaynes, 2003). Cox (1946) argued that the rules of probability follow from desiderata for the plausible reasoning of a rational agent, an argument Jaynes (2003) elaborated into a systematic Bayesian treatment. The sufficiency of Cox's assumptions has been debated in the philosophical literature, so the derivation is best described as a motivation for the Bayesian calculus, not a universally accepted proof.

Computation was the main historical obstacle to Bayesian practice, since posteriors usually lack closed forms. Metropolis et al. (1953) introduced the sampling algorithm that became the basis of Markov chain Monte Carlo (MCMC), and Hastings (1970) generalized it. Pearl (1988) introduced belief networks and efficient inference by message passing, bringing Bayesian reasoning into mainstream AI. Variational methods, reviewed for statisticians by Blei, Kucukelbir and McAuliffe (2017), recast inference as optimization and made approximate Bayesian inference feasible at scale. Kingma and Welling (2014) combined variational inference with neural networks in the variational autoencoder. Textbook treatments that unify these developments for machine learning include Bishop (2006) and Murphy (2022).

#4.1 Probability as a calculus

A probability measure assigns to events $A$ numbers in $[0,1]$ such that the whole space has probability 1 and probabilities of disjoint events add. For random variables, the key identities are the product rule and sum rule:

Two variables are independent if $p(x,y) = p(x)p(y)$ and conditionally independent given $z$ if $p(x,y \mid z) = p(x \mid z)p(y \mid z)$. Expectation is $\mathbb{E}[f(X)] = \sum_x f(x)p(x)$ (or an integral).

#4.2 Bayes' theorem

For parameters $\theta$ and data $D$,

Here $p(\theta)$ is the prior, $p(D \mid \theta)$ the likelihood, $p(\theta \mid D)$ the posterior, and $p(D)$ the marginal likelihood or evidence. Predictions integrate over the posterior:

#4.3 A closed-form example

Let a binary outcome have unknown success probability $\theta$ with prior $\theta \sim \mathrm{Beta}(a, b)$. After observing $k$ successes in $n$ independent trials, the posterior is

The prior acts like $a+b$ pseudo-observations. As $n$ grows, the posterior concentrates near $k/n$ and the influence of the prior diminishes. This conjugacy is the exception: most useful models have no closed-form posterior.

#4.4 Point estimates and their relation to loss functions

• Maximum likelihood (MLE): $\hat\theta_{\text{MLE}} = \arg\max_\theta \log p(D \mid \theta)$.
• Maximum a posteriori (MAP): $\hat\theta_{\text{MAP}} = \arg\max_\theta \bigl[\log p(D \mid \theta) + \log p(\theta)\bigr]$.

For a regression model with Gaussian noise, MLE is equivalent to minimizing squared error; for a classifier with a categorical output, it is equivalent to minimizing cross-entropy. MAP with a zero-mean Gaussian prior on weights corresponds to $L_2$ regularization (weight decay) of the loss, a standard correspondence (Bishop, 2006). Neural-network training as usually practised yields a point estimate, not a posterior.

#4.5 Approximate inference

• MCMC constructs a Markov chain whose stationary distribution is the posterior (Metropolis et al., 1953; Hastings, 1970). It is asymptotically exact but can be slow for high-dimensional models.
• Variational inference chooses a tractable family $q_\phi(\theta)$ and maximizes the evidence lower bound

which is equivalent to minimizing the KL divergence $\mathrm{KL}(q_\phi(\theta) \,\|\, p(\theta \mid D))$ (Blei et al., 2017). The same bound underlies the variational autoencoder (Kingma & Welling, 2014).

• Ensembles and other approximations are used to estimate predictive uncertainty in deep networks; they are heuristic approximations to a Bayesian posterior and their fidelity is variable.

#4.6 Frequentist versus Bayesian statements

A frequentist 95% confidence interval is a procedure that covers the true parameter in 95% of repeated samples; it is not a probability statement about the parameter in the realized sample. A Bayesian 95% credible interval is a statement about the posterior distribution, conditional on the model and prior. Both are valid under their own definitions of probability. Disagreement concerns interpretation, the role of priors, and the handling of model misspecification, and is discussed in Gelman et al. (2013).

#4.7 Graphical models

A Bayesian network factorizes a joint distribution according to a directed acyclic graph: $p(x_1,\dots,x_n) = \prod_i p(x_i \mid \mathrm{pa}(x_i))$. Conditional independence is read from graph structure, and message-passing algorithms exploit it for efficient inference in tree-structured and some other graphs (Pearl, 1988). General exact inference is computationally hard (see FOUND-004 Computational Complexity in AI).

Schools and interpretations. Frequentist (probability as long-run frequency), subjective Bayesian (probability as degree of belief), objective Bayesian (priors constrained by principles such as maximum entropy; Jaynes, 2003). The choice affects method more than mathematics: the probability axioms are common to all.

Model classes.

• Discriminative models learn $p(y \mid x)$ directly.
• Generative models learn $p(x)$ or $p(x, y)$ (including autoregressive language models and variational autoencoders).
• Latent-variable models introduce unobserved variables whose posteriors must be inferred.
• Probabilistic graphical models encode structured dependencies (Pearl, 1988).

Inference methods. Exact (conjugacy, enumeration, message passing), sampling (MCMC), and variational approximation.

Notions of uncertainty. Aleatoric uncertainty reflects irreducible noise in the data-generating process; epistemic uncertainty reflects lack of knowledge about the model and can in principle be reduced with data. The distinction is conceptually useful, though separating the two in practice is difficult and is itself debated.

• Probabilistic classification and language modelling. Language models are trained by minimizing the negative log-likelihood of next tokens (see TECH-LLM-001 Large Language Models).
• Spam filtering and diagnosis. Naive Bayes and Bayesian network classifiers are textbook examples (Bishop, 2006; Pearl, 1988).
• Generative modelling. Variational autoencoders optimize the evidence lower bound (Kingma & Welling, 2014).
• Model assessment. Calibration: Guo et al. (2017) examined modern neural-network classifiers and reported that they tended to be less well calibrated than older, smaller networks, and that a simple post-hoc temperature scaling often improved calibration. That finding concerned the image and text classification models they evaluated and should not be extended to all current systems without testing. See also CAP-LIMITS-001 Hallucination, Reliability and Calibration.
• Scientific inference. Hierarchical Bayesian models are standard in applied statistics (Gelman et al., 2013).

Distinguish these deployed uses from research demonstrations: scalable, fully Bayesian training of very large neural networks remains primarily a research topic.

Advantages. A single consistent calculus; explicit treatment of uncertainty; natural regularization through priors; principled model comparison via marginal likelihoods; graceful handling of small data when informative priors are available.

Limitations.

• Computation: posterior integrals are intractable for most models, and approximations (variational, MCMC, ensembles) introduce error whose size is hard to assess.
• Prior specification: results can depend on priors, especially with limited data. "Uninformative" priors are not uniquely defined.
• Model misspecification: Bayesian updating is coherent within a model but offers no guarantee when the model class excludes the truth.
• Calibration of deep networks: probability outputs from neural networks need not be calibrated probabilities (Guo et al., 2017).
• Overinterpretation: the softmax output of a classifier is not by itself a posterior probability.

Open questions. How to obtain trustworthy uncertainty from very large models at acceptable cost; how to specify priors for high-dimensional models; whether a Bayesian description captures human or machine cognition (a descriptive claim distinct from the normative one); and the proper reading of Cox-style derivations.

As of 2026-10-15:

• The probability calculus, Bayes' theorem, and the equivalence between MLE and common loss functions are Established.
• MCMC and variational inference are mature, widely used methods whose theory and limitations are documented in textbooks and reviews (Gelman et al., 2013; Blei et al., 2017).
• The calibration findings of Guo et al. (2017) are Well Supported for the models studied there; calibration of current large language models is an active empirical area, and quantitative claims should be taken from current evaluations (see MODEL-001).
• The assertion that the Bayesian framework is the uniquely rational basis for belief revision is Contested. Many statisticians accept Bayesian methods as one tool among several and evaluate methods by frequentist performance.

No registered forecast is made here. Observed directions include: scalable approximate Bayesian methods for large networks; post-hoc and conformal-style uncertainty quantification; probabilistic treatments of safety-relevant risk estimation; and tighter integration of causal reasoning with probabilistic models. Near-term development is expected to be incremental. Statements that Bayesian methods will become the default for large-scale deep learning are speculative and not supported by a source here.

• Foundational Concepts:
  • FOUND-004 Computational Complexity in AI: why exact inference is often intractable.
  • FOUND-002 Definitions of Intelligence: rational belief revision and agency.
• Related Methods & Technologies:
  • FOUND-007 Learning, Reasoning and Generalization: risk, generalization and inductive bias.
  • FOUND-009 Information Theory: entropy, KL divergence and cross-entropy.
  • FOUND-010 Optimization and Gradient Descent: how likelihoods and ELBOs are maximized.
  • TECH-ML-001 Machine Learning: probabilistic learning methods.
  • TECH-VAE-001 Autoencoders and Variational Autoencoders: variational inference in neural networks.
• Advanced Implications & Future Trajectories:
  • FOUND-012 Game Theory and Decision Theory: probabilities combined with utilities.
  • CAP-LIMITS-001 Hallucination, Reliability and Calibration: calibration of deployed systems.

Information theory is the mathematical study of the quantification, storage and communication of information. Founded by Claude Shannon in 1948, it defines the entropy of a probability distribution as the average uncertainty (or minimum average description length) of its outcomes, and provides the limits of lossless compression and of reliable communication over noisy channels. In machine learning its quantities, entropy, cross-entropy, KL divergence and mutual information, serve as loss functions, similarity measures and analytic tools.

Information theory supplies precise answers to two engineering questions: how compactly can data from a source be represented, and how fast can data be sent reliably through a noisy channel? Shannon's (1948) results showed that both have sharp limits determined by the statistics of the source and the channel, and that these limits are achievable in principle.

For AI the significance is largely through three routes.

1. Training objectives. Cross-entropy, the standard loss for classification and language modelling, is an information-theoretic quantity (FOUND-008 Probability, Statistics and Bayesian Inference).
2. Prediction and compression. A model that predicts data well can be used to compress it, and vice versa. This equivalence supports a view of learning as finding regularities that shorten descriptions.
3. Theories of representation. Concepts such as the information bottleneck propose that good representations retain information relevant to a task while discarding the rest.

Shannon's theory defines information in terms of statistical structure and ignores meaning. It is therefore a theory of the quantity of information, which is distinct from questions of semantics and understanding (see FOUND-014 Consciousness and Machine Understanding).

Shannon's "A Mathematical Theory of Communication" (1948), published in the Bell System Technical Journal, introduced entropy as a measure of the information produced by a source, the notion of channel capacity, and the coding theorems that relate them. Shannon was also a participant in the 1956 Dartmouth workshop and wrote on computer chess (BIO-SHANNON-001 Claude Shannon).

Subsequent milestones include Huffman's (1952) method for constructing minimum-redundancy prefix codes, Kullback and Leibler's (1951) measure of divergence between distributions, and Jaynes's (1957) principle of maximum entropy, which proposed choosing the least-committal distribution consistent with known constraints and linked statistical mechanics with inference. Solomonoff (1964) formulated a theory of inductive inference based on algorithmic descriptions of data, an early root of algorithmic information theory, in which complexity is measured by the length of the shortest program that generates an object.

Textbook syntheses are provided by Cover and Thomas (2006) and MacKay (2003); the latter explicitly links information theory with inference and learning.

In the deep learning era, Tishby and Zaslavsky (2015) proposed analysing deep networks through the information bottleneck principle. A critical study by Saxe et al. (2019) challenged key empirical claims associated with that proposal (Section 7). More recently, Delétang et al. (2023) revisited the prediction-compression link for large language models.

#4.1 Entropy

For a discrete random variable $X$ with distribution $p$, the Shannon entropy is

measured in bits when the logarithm has base 2 (nats for the natural logarithm). It is zero for a deterministic variable and maximal, $\log_2 |\mathcal{X}|$, for the uniform distribution. Joint and conditional entropies are defined analogously, with the chain rule $H(X,Y) = H(X) + H(Y \mid X)$.

#4.2 Source coding

Shannon's source coding theorem states that the entropy is the minimum average number of bits per symbol needed to encode i.i.d. symbols from the source without loss, in the limit of long messages (Shannon, 1948; Cover & Thomas, 2006). Practical codes approach this bound; Huffman (1952) codes are optimal among symbol-by-symbol prefix codes. An ideal code assigns a symbol of probability $p$ a length of about $-\log_2 p$ bits.

#4.3 Cross-entropy and KL divergence

If data are drawn from $p$ but encoded using a code optimized for a model $q$, the average code length is the cross-entropy

where the Kullback-Leibler divergence (Kullback & Leibler, 1951) is

with equality only when $p = q$. KL divergence is not symmetric and is not a metric. Minimizing cross-entropy between the empirical data distribution and a model is therefore equivalent to maximum likelihood estimation, and the excess over the data entropy $H(p)$ is the KL divergence.

For a language model, the average negative log-probability per token on held-out text is its cross-entropy, and perplexity is its exponential, $\mathrm{PPL} = 2^{H(p,q)}$ for entropy in bits, which can be read as an effective branching factor.

#4.4 Mutual information

measures how much knowing one variable reduces uncertainty about the other. It is zero if and only if $X$ and $Y$ are independent. Mutual information is used in feature selection, representation learning objectives, and analyses of what a representation preserves.

#4.5 Channel capacity

For a noisy channel with input $X$ and output $Y$, the capacity is $C = \max_{p(x)} I(X;Y)$. Shannon's noisy-channel coding theorem states that reliable communication is possible at any rate below $C$ and impossible above it (Shannon, 1948). The theorem is existential: it does not provide a practical code.

#4.6 Maximum entropy

Among all distributions satisfying given expected-value constraints, the maximum-entropy distribution is the one with the greatest uncertainty, and it takes an exponential-family form (Jaynes, 1957). Many familiar models, including logistic regression and the Gaussian under fixed mean and variance, have maximum-entropy derivations.

#4.7 Algorithmic information

The Kolmogorov complexity of a string is the length of the shortest program producing it on a fixed universal machine. It is uncomputable and defined up to an additive constant, but gives a conceptual basis for "simplicity" in learning. Solomonoff (1964) used such descriptions to define a universal prior for prediction. Practical systems use computable proxies such as compression ratios.

• Quantities: entropy, conditional entropy, cross-entropy, KL divergence, mutual information.
• Coding: lossless (Huffman and other entropy coding) and lossy (rate-distortion theory).
• Discrete versus differential entropy: the continuous analogue (differential entropy) can be negative and is not invariant under change of variables, so interpretation differs from the discrete case.
• Classical versus algorithmic information theory: the first is defined over distributions, the second over individual objects.
• Information-theoretic principles in learning: maximum entropy (Jaynes, 1957), minimum description length, the information bottleneck (Tishby & Zaslavsky, 2015).

• Training losses. Cross-entropy for classification and next-token prediction; KL terms in the variational autoencoder objective (TECH-VAE-001 Autoencoders and Variational Autoencoders); KL penalties in reinforcement-learning-based fine-tuning.
• Data compression. Entropy coding is a deployed component of file, image and video formats; Huffman coding is a standard example (Huffman, 1952).
• Language modelling as compression. Delétang et al. (2023) argue that prediction and compression are equivalent via arithmetic coding, and evaluate large language models as general-purpose compressors on text, image and audio data; their results are laboratory evaluations of compression ratio and do not by themselves show that compression performance measures understanding.
• Evaluation. Perplexity is a standard intrinsic metric for language models, but it depends on tokenization and dataset and is not directly comparable across models with different vocabularies.
• Communications. Capacity-approaching error-correcting codes in wireless and storage systems rest on Shannon's theorems (Cover & Thomas, 2006).

Strengths. Rigorous, general, and mathematically tractable; provides tight bounds for compression and communication; unifies several learning objectives.

Limitations.

• Shannon information is defined relative to a probability model. Its value depends on that model, and it is blind to semantic content.
• Mutual information is hard to estimate reliably in high dimensions from finite samples.
• Kolmogorov complexity and Solomonoff induction are uncomputable; they serve as idealizations (Solomonoff, 1964).
• Information bottleneck in deep learning. Tishby and Zaslavsky (2015) proposed that deep networks can be analysed as trading compression of the input against retention of information about the label. Saxe et al. (2019) reported that some of the claimed compression phases depend on the activation function and measurement method, and did not observe a general link between compression and generalization. The status of the proposal as a general theory of deep learning is therefore Contested.

Open questions. Whether information-theoretic quantities explain generalization in large networks; how to measure information in learned representations robustly; and the relation between compression and intelligence (an argument discussed in FOUND-002 Definitions of Intelligence).

As of 2026-10-15:

• Shannon's coding theorems, the properties of entropy, KL divergence and mutual information, and the cross-entropy/maximum-likelihood equivalence are Established and standard in textbooks (Cover & Thomas, 2006; MacKay, 2003).
• The statement that good prediction implies good compression, via arithmetic coding, is a mathematical equivalence; its use to evaluate trained language models is documented in a preprint-stage and conference literature (Delétang et al., 2023, an arXiv preprint). [VERIFICATION NEEDED: final venue and publication status of Delétang et al. (2023)]
• The information bottleneck as an explanation of deep learning dynamics is Contested (Tishby & Zaslavsky, 2015; Saxe et al., 2019).

No registered forecast is made. Observed trends: continued use of information-theoretic objectives in generative modelling; research on compression-based evaluation of language models; and efforts to relate representation quality to measurable information. Speculation that a compression principle alone could characterize general intelligence is a hypothesis, not a result, and is discussed with its objections in the definitional literature (FOUND-002 Definitions of Intelligence).

• Foundational Concepts:
  • FOUND-008 Probability, Statistics and Bayesian Inference: distributions, likelihood and Bayesian objectives.
• Related Methods & Technologies:
  • FOUND-007 Learning, Reasoning and Generalization: generalization and inductive bias.
  • FOUND-010 Optimization and Gradient Descent: minimizing information-theoretic losses.
  • TECH-LLM-001 Large Language Models: cross-entropy training and perplexity.
  • TECH-VAE-001 Autoencoders and Variational Autoencoders: KL terms in latent-variable models.
• Advanced Implications & Future Trajectories:
  • BIO-SHANNON-001 Claude Shannon: the founder of the field.
  • FOUND-014 Consciousness and Machine Understanding: information versus meaning.

Optimization is the problem of finding parameters that minimize (or maximize) an objective function, possibly subject to constraints. Gradient descent is an iterative first-order method that repeatedly moves the parameters in the direction of the negative gradient of the objective; its stochastic variants, which estimate the gradient from small random subsets of data, are the standard means of training neural networks.

Most machine learning is framed as minimizing a loss $L(\theta)$ over parameters $\theta$ (FOUND-007 Learning, Reasoning and Generalization). Whether a model learns well depends on its architecture and data, and also on how the optimizer navigates the loss landscape. In deep learning the parameter count can be very large and the loss is non-convex, so exact minimization is infeasible and the relevant questions become: how fast does the method make progress, where does it end up, and how does the end point generalize?

Gradient-based training became practical through backpropagation, which computes gradients of a network's loss efficiently (Rumelhart et al., 1986; see TECH-BACKPROP-001 Backpropagation). Optimization is thus the link between a model specification and a trained system, and choices such as learning rate, batch size and optimizer are significant engineering decisions in large-scale training (TECH-DL-001 Deep Learning).

Gradient descent is usually attributed to Cauchy in the nineteenth century. This article does not cite the primary source and treats the attribution as conventional. [VERIFICATION NEEDED: primary source for the Cauchy attribution] Robbins and Monro (1951) introduced stochastic approximation, the basis of stochastic gradient descent (SGD): iterating with noisy gradient estimates and decreasing step sizes converges under conditions. Polyak (1964) introduced the heavy-ball momentum method to speed convergence on ill-conditioned problems.

Rumelhart, Hinton and Williams (1986) showed that gradient descent with backpropagated gradients could train multi-layer networks to learn useful internal representations, a milestone in the connectionist revival (HIST-008 Backpropagation and the Connectionist Revival). Adaptive per-parameter methods followed, including Adam (Kingma & Ba, 2015), and Loshchilov and Hutter (2019) proposed decoupling weight decay from the gradient update (AdamW). Bottou, Curtis and Nocedal (2018) provide a comprehensive review of optimization methods for large-scale machine learning. Standard theoretical background in convex optimization is in Boyd and Vandenberghe (2004), and a deep-learning-oriented treatment is in Goodfellow, Bengio and Courville (2016).

#4.1 Gradient descent

For a differentiable objective $L(\theta)$, gradient descent iterates

where $\eta > 0$ is the learning rate. The negative gradient is the direction of steepest local decrease. For a convex function whose gradient is $\beta$-Lipschitz ($\beta$-smooth), the choice $\eta = 1/\beta$ gives $L(\theta_k) - L(\theta^*) = O(1/k)$, a standard result (Boyd & Vandenberghe, 2004; Bottou et al., 2018). For strongly convex functions the convergence is linear (geometric). Neither guarantee applies directly to neural-network losses, which are non-convex.

#4.2 Stochastic and mini-batch gradients

With a training objective $L(\theta) = \frac{1}{N}\sum_{i=1}^N \ell_i(\theta)$, computing the full gradient costs $O(N)$ per step. SGD replaces it with an unbiased estimate from a random mini-batch $B$:

Each step is cheap, and the noise can help escape poor regions. Convergence analyses require step sizes that decay or are small enough to control variance (Robbins & Monro, 1951; Bottou et al., 2018). Larger batches reduce gradient variance but increase cost per step.

#4.3 Momentum

Momentum accumulates a velocity:

with $\mu \in [0,1)$. It damps oscillations in directions of high curvature and accelerates progress along consistent directions (Polyak, 1964).

#4.4 Adaptive methods

Adam maintains exponential moving averages of the gradient $g_t$ and its square:

and updates $\theta_{t+1} = \theta_t - \eta\,\hat m_t / (\sqrt{\hat v_t} + \epsilon)$, where $\hat m_t$ and $\hat v_t$ are bias-corrected (Kingma & Ba, 2015). Each parameter thus has its own effective step size. AdamW applies weight decay directly to the parameters, separately from the adaptive gradient scaling (Loshchilov & Hutter, 2019).

#4.5 Learning-rate schedules and practicalities

Learning rate is typically varied over training (warm-up, decay). Gradient clipping, normalization layers and mixed-precision arithmetic address numerical stability. The choices are largely empirical; no single schedule is optimal across problems.

#4.6 The loss landscape

Neural-network losses have many parameters, saddle points and flat regions. Dauphin et al. (2014) argued, using ideas from statistical physics and empirical evidence, that in high dimensions saddle points rather than poor local minima are the principal obstacle to optimization. Choromanska et al. (2015) analysed the loss surfaces of multilayer networks under simplifying assumptions and related the structure of critical points to network size. These analyses rely on assumptions that do not fully match practical networks, and they are best regarded as suggestive.

#4.7 Regularization as optimization

Explicit penalties (for example, $L_2$ weight decay) change the objective; optimizer choice and early stopping act as implicit regularizers. Which solutions SGD-like methods select among the many that fit the training data, and why those solutions generalize, is a research question.

• First-order methods: gradient descent, SGD, momentum, Nesterov-type acceleration, adaptive methods (AdaGrad, RMSProp, Adam, AdamW).
• Second-order and quasi-Newton methods: use curvature information (Hessian approximations); costly for models with very many parameters, so used mainly at smaller scale or through approximations.
• Derivative-free and evolutionary methods: used where gradients are unavailable (black-box tuning, some reinforcement learning settings).
• Convex versus non-convex problems: convex problems have global-optimality guarantees (Boyd & Vandenberghe, 2004); neural-network training is non-convex.
• Constrained and discrete optimization: relevant to planning, scheduling and combinatorial search (FOUND-004 Computational Complexity in AI).

• Training neural networks with SGD or Adam-family optimizers is the standard practice in deep learning (Kingma & Ba, 2015; Goodfellow et al., 2016). The AdamW variant is widely used for transformer training; because training recipes change, current practice should be checked against recent technical reports and the relevant Living Reference entries.
• Linear and logistic regression, support vector machines: convex problems solved by gradient or quasi-Newton methods (Bishop, 2006).
• Large-batch training. Keskar et al. (2017) reported that large-batch methods tended to converge to sharper minima and showed a generalization gap in their experiments. Subsequent work has examined whether the gap is intrinsic or can be mitigated with tuning; the conclusion in the original paper is therefore Contested in general.
• Adaptive versus non-adaptive generalization. Wilson et al. (2017) reported cases in which adaptive methods generalized worse than SGD with momentum when tuned comparably; this does not imply that adaptive methods are inferior in general.

Strengths. Gradient methods are simple, scale to billions of parameters when combined with data and model parallelism, and work with any differentiable model.

Limitations.

• No global-optimality guarantee for non-convex losses.
• Sensitivity to hyperparameters (learning rate, batch size, schedule); instability and divergence are common failure modes.
• Vanishing and exploding gradients in deep or recurrent architectures.
• Optimizing a proxy loss does not guarantee that the downstream objective is met; a model can minimize its training loss while failing on goals the loss does not capture (relevant to SAFE-ALIGN-001 AI Alignment).

Open questions. Why simple first-order methods find solutions that generalize in over-parameterized networks; the relationship between flat minima and generalization (Keskar et al., 2017, and critics); whether the saddle-point picture of Dauphin et al. (2014) fully accounts for training dynamics; and optimizer behaviour at frontier scale.

As of 2026-10-15:

• Convergence results for convex smooth objectives and for SGD under standard assumptions are Established (Boyd & Vandenberghe, 2004; Bottou et al., 2018).
• SGD and Adam-family optimizers are the dominant practical choice for training neural networks (Goodfellow et al., 2016; Kingma & Ba, 2015); specific hyperparameters used by named frontier models are mostly undisclosed or change quickly and are not tabulated here.
• The relative generalization of adaptive and non-adaptive methods, and the role of batch size and sharpness, are Contested (Wilson et al., 2017; Keskar et al., 2017).
• The picture that saddle points rather than local minima dominate difficulty in high dimensions is Preliminary to Well Supported, depending on the model class (Dauphin et al., 2014; Choromanska et al., 2015).

No registered forecast is made. Observed research directions include second-order and preconditioned methods that remain tractable at scale, optimizers designed for very large batch sizes and low-precision arithmetic, and theory of implicit regularization. Near-term change is likely to be incremental refinements of existing optimizers rather than replacement of gradient-based training. Claims that a particular new optimizer will supersede Adam-family methods should be evaluated against independent, well-tuned baselines.

• Foundational Concepts:
  • FOUND-008 Probability, Statistics and Bayesian Inference: likelihood objectives that are optimized.
  • FOUND-007 Learning, Reasoning and Generalization: empirical risk minimization and generalization.
  • FOUND-009 Information Theory: cross-entropy losses.
• Related Methods & Technologies:
  • TECH-BACKPROP-001 Backpropagation: computing the gradients.
  • TECH-DL-001 Deep Learning: the main application setting.
  • TECH-RL-001 Reinforcement Learning: policy-gradient optimization.
  • HIST-008 Backpropagation and the Connectionist Revival: the historical context.
• Advanced Implications & Future Trajectories:
  • TECH-SCALE-001 Scaling Laws: how loss behaves under optimization at scale.
  • SAFE-ALIGN-001 AI Alignment: optimization of proxy objectives.

Logic is the study of valid inference. A formal system specifies a precise language, a set of axioms and a set of inference rules from which theorems can be derived by purely syntactic steps, so that correctness of a derivation can be checked mechanically. In AI, logic provides representation languages for knowledge, algorithms for deriving consequences, and limits on what any such algorithm can accomplish.

Logic was the first major formalism for AI. The early programs of the 1950s and 1960s (see HIST-003 Symbolic AI and the Perceptron) treated intelligence as symbol manipulation, with logical deduction as a model of reasoning. McCarthy's research program proposed representing common-sense knowledge in logical form, and logic-based representation remains the core of knowledge representation languages, databases, program verification and formal mathematics (FOUND-003 Knowledge Representation).

Logic also delimits what is possible. Results of Gödel, Church and Turing show that sufficiently expressive formal systems cannot be both complete and decidable, and complexity theory (Cook, 1971; see FOUND-004 Computational Complexity in AI) shows that even propositional satisfiability is believed to be intractable in the worst case. These limits explain both the successes (exact, verifiable reasoning in restricted domains) and the difficulties (brittleness, combinatorial explosion) of logic-based AI.

Current interest in logic comes from two directions: the use of proof assistants and automated provers for verified mathematics and software, and attempts to combine neural networks, which learn flexibly but give no guarantees, with symbolic reasoning, which gives guarantees but requires formalization (Garcez & Lamb, 2023).

Modern formal logic dates from the late nineteenth century and the construction of quantificational logic as a formal language (Frege's Begriffsschrift, 1879) [VERIFICATION NEEDED: Frege primary source not checked]. In 1931 Gödel proved that any consistent, effectively axiomatized formal system capable of expressing elementary arithmetic is incomplete: there are true statements it cannot prove (Gödel, 1931). In 1936 Church and Turing independently showed that the Entscheidungsproblem, the problem of deciding validity of first-order formulas, has no algorithmic solution (Church, 1936; Turing, 1936-37). Turing's paper also introduced the abstract machine now called the Turing machine (BIO-TURING-001 Alan Turing).

In AI, Newell and Simon's Logic Theory Machine (1956) is generally regarded as an early program that proved theorems of propositional logic (Newell & Simon, 1956). Davis, Logemann and Loveland (1962) published a procedure for propositional theorem proving that is the ancestor of modern SAT solvers. Robinson (1965) introduced the resolution principle, a single inference rule suitable for machine implementation in first-order logic. Cook (1971) showed that propositional satisfiability is NP-complete, linking logic with complexity theory.

By the 1970s, researchers noted that classical logic is monotonic (adding premises never removes conclusions), which conflicts with everyday reasoning that retracts conclusions on new information. Reiter (1980) proposed default logic as a formalization of reasoning with defaults, one of several non-monotonic formalisms. Description logics, which restrict first-order logic to obtain decidable fragments, underlie ontology languages used in knowledge representation.

Recent work includes machine-learning systems that interact with formal proof systems. Polu and Sutskever (2020) trained a language model to generate proofs for the Metamath formalization. De Moura and Ullrich (2021) describe the Lean 4 theorem prover and programming language. Trinh et al. (2024) combined a language model with a symbolic deduction engine for Euclidean geometry.

#4.1 Syntax and semantics

A logic has a syntax (which strings are well-formed formulas) and a semantics (what formulas mean, typically via truth in models). Propositional logic has atomic propositions combined by connectives ($\neg, \wedge, \vee, \rightarrow$). First-order logic adds objects, predicates, functions and quantifiers $\forall, \exists$, for example

#4.2 Entailment, soundness and completeness

A set of formulas $\Gamma$ entails $\varphi$, written $\Gamma \models \varphi$, if $\varphi$ is true in every model of $\Gamma$. A proof system derives $\Gamma \vdash \varphi$ by syntactic rules. The system is sound if $\Gamma \vdash \varphi$ implies $\Gamma \models \varphi$, and complete if the converse holds. First-order logic admits sound and complete proof systems, so valid formulas are semi-decidable: a procedure exists that halts with a proof for every valid formula, but none can halt on every invalid one (Church, 1936; Turing, 1936-37; Robinson, 1965).

#4.3 Resolution and satisfiability

In resolution, formulas are converted to clausal form, and two clauses containing complementary literals are resolved to produce a new clause:

To prove $\Gamma \models \varphi$, one adds $\neg\varphi$ to $\Gamma$ and derives the empty clause (refutation), which signals unsatisfiability (Robinson, 1965). For propositional logic, the DLL procedure performs systematic search with unit propagation and backtracking (Davis et al., 1962), and modern conflict-driven solvers extend it. Satisfiability is NP-complete (Cook, 1971), so worst-case runtime is expected to be exponential even though many practical instances are solved quickly.

#4.4 Incompleteness

Gödel's first incompleteness theorem states that for any consistent, effectively axiomatized theory that includes a sufficient amount of arithmetic, there is a sentence that is true but unprovable in the theory (Gödel, 1931). The theorem limits what any formal system, including one used by an AI system, can prove about arithmetic. Claims that it limits machine intelligence relative to human intelligence require additional, contested philosophical premises and are not consequences of the theorem alone (FOUND-005 Philosophy of Mind and the Turing Test).

#4.5 Non-monotonic and uncertain reasoning

In default logic, a default rule has the form "if $\alpha$ holds and it is consistent to assume $\beta$, conclude $\gamma$" (Reiter, 1980). Probabilistic formalisms address uncertainty differently, representing degrees of belief rather than defaults (FOUND-008 Probability, Statistics and Bayesian Inference).

#4.6 Machine-checkable proof

Proof assistants such as Lean check every step of a proof against a small trusted kernel, so a verified proof is correct relative to the kernel and the stated definitions (de Moura & Ullrich, 2021). This property allows learned systems to propose proofs while a formal checker rejects invalid ones, as in the proof-search setting of Polu and Sutskever (2020).

• Propositional logic: decidable (satisfiability is NP-complete).
• First-order logic: expressive and semi-decidable.
• Higher-order and type-theoretic logics: used in proof assistants such as Lean.
• Modal and temporal logics: reasoning about necessity, knowledge, time; used in verification.
• Description logics: decidable fragments for ontologies.
• Non-monotonic logics: default logic and related systems (Reiter, 1980).
• Probabilistic and fuzzy logics: handle graded truth or uncertainty.
• Automated reasoning technologies: SAT and SMT solvers, resolution provers, interactive proof assistants.
• Neurosymbolic approaches: combine learned components with symbolic reasoning (Garcez & Lamb, 2023).

• Hardware and software verification. SAT/SMT solving and theorem proving are used to check designs and programs; the deductive core of these tools descends from Davis et al. (1962) and Robinson (1965).
• Knowledge-based systems and ontologies. Description logic reasoners support classification in large ontologies (FOUND-003 Knowledge Representation).
• Formal mathematics. Lean and similar systems are used for large formalization projects (de Moura & Ullrich, 2021).
• Neurosymbolic research demonstrations. AlphaGeometry (Trinh et al., 2024) reported solving 25 of 30 olympiad-level geometry problems in its test set, compared with ten for the previous best method it reported, using a language model to guide a symbolic deduction engine. This is a result for a specific problem set in one domain and a laboratory demonstration.
• Learned proof search. Polu and Sutskever (2020) is a research demonstration of language-model proof generation checked by a formal verifier.

Strengths. Soundness guarantees; transparent, inspectable derivations; precise semantics; the ability to verify results independently of how they were found.

Limitations.

• Undecidability and intractability: first-order validity is undecidable, and propositional satisfiability is NP-complete (Church, 1936; Turing, 1936-37; Cook, 1971).
• Incompleteness of sufficiently rich theories (Gödel, 1931).
• The knowledge acquisition bottleneck: reasoning requires formalized knowledge, which is costly to write and incomplete.
• Brittleness: classical logic handles exceptions, uncertainty and vagueness poorly without extensions (Reiter, 1980).
• Autoformalization gap: translating informal problems into formal statements is itself a hard problem; systems that work in formal settings do not automatically transfer to informal mathematics.

Open questions. How best to integrate learned and symbolic reasoning; whether neural models can learn reliable deduction without explicit symbolic machinery; and how to scale formalization of knowledge.

As of 2026-10-15:

• The metatheoretic results (completeness of first-order logic, undecidability, incompleteness, NP-completeness of SAT) are Established.
• Practical SAT/SMT solvers and proof assistants are mature, deployed technologies.
• Learned proof search and neurosymbolic systems are active research. The reported results (Polu & Sutskever, 2020; Trinh et al., 2024) are Well Supported as demonstrations on the cited benchmarks, but their generality is Contested. Current performance of language models on formal mathematics changes rapidly and is tracked outside this stable article (see TECH-REASON-001 Reasoning Models and Test-Time Compute and MODEL-001).
• The debate whether symbolic structure is necessary for general intelligence, or whether it can emerge in neural networks, is Contested (Garcez & Lamb, 2023, argue for the neurosymbolic approach).

No registered forecast is made. Observed trends: growth in machine-checked mathematics and in AI systems that propose proofs for formal verification; research on combining language models with solvers and provers; and interest in using formal methods to verify properties of AI-enabled systems. Whether formal verification can provide guarantees about large learned models is an open question rather than a demonstrated capability.

• Foundational Concepts:
  • FOUND-003 Knowledge Representation: logic as a representation language.
  • FOUND-004 Computational Complexity in AI: complexity limits on reasoning.
• Related Methods & Technologies:
  • FOUND-007 Learning, Reasoning and Generalization: deduction versus induction.
  • HIST-003 Symbolic AI and the Perceptron: early logic-based AI.
  • BIO-TURING-001 Alan Turing: computability.
• Advanced Implications & Future Trajectories:
  • TECH-REASON-001 Reasoning Models and Test-Time Compute: learned reasoning in language models.
  • CAP-REASON-001 Reasoning, Planning and Long-Horizon Capability: measured reasoning capability.

Decision theory studies how an agent should choose among actions whose outcomes are uncertain, typically by maximizing expected utility. Game theory extends the analysis to settings with several decision-makers whose outcomes depend on one another's choices. Together they define the standard formal model of a rational agent used in AI, and the basis for analysing cooperation, competition and strategic behaviour among AI systems.

The textbook definition of an AI system as a rational agent that acts to maximize expected performance (Russell & Norvig, 2020) is a decision-theoretic definition. Reinforcement learning, planning under uncertainty and preference-based training all assume an objective (utility or reward) that the agent optimizes (TECH-RL-001 Reinforcement Learning). Probability supplies the uncertainty model (FOUND-008 Probability, Statistics and Bayesian Inference); utility supplies the preferences.

Game theory matters wherever agents interact: adversarial settings such as poker and negotiation, adversarial training objectives, multi-agent systems, and the strategic behaviour of AI developers and states. It also frames safety questions. Specifying an objective for an agent is a decision-theoretic design problem (SAFE-ALIGN-001 AI Alignment), and some formulations of alignment cast it as a game between a human and an AI (Hadfield-Menell et al., 2016).

A limit of the framework deserves stating at the outset. Expected-utility theory is a normative model of rational choice and a convenient design abstraction; observed human behaviour deviates from it in systematic ways, and real AI systems seldom have an explicit utility function.

Modern game theory is generally dated to von Neumann and Morgenstern's Theory of Games and Economic Behavior (1944), which developed the theory of zero-sum games and gave an axiomatic derivation of expected-utility maximization from preferences over lotteries (von Neumann & Morgenstern, 1944/2007). Nash (1950) proved that finite games have equilibrium points in mixed strategies, extending the analysis to non-zero-sum settings.

The empirical and descriptive limits of expected utility were identified early. Ellsberg (1961) described choices under ambiguity that violate the Savage axioms of subjective expected utility. Kahneman and Tversky (1979) proposed prospect theory to describe observed choices under risk.

Evolutionary and cooperative themes emerged with Axelrod and Hamilton (1981), who analysed the iterated Prisoner's Dilemma, including the results of a computer tournament, and showed how cooperation based on reciprocity can arise and persist under their model's assumptions.

Computational game theory began to matter for AI when complexity was understood. Daskalakis, Goldberg and Papadimitriou (2009) showed that computing a Nash equilibrium is complete for the complexity class PPAD, which gives evidence that there is no efficient general algorithm. In AI practice, algorithms for imperfect-information games reached professional-level poker (Moravčík et al., 2017; Brown & Sandholm, 2018), then six-player poker (Brown & Sandholm, 2019), and an agent combining language models with planning achieved strong results in the negotiation game Diplomacy (Meta Fundamental AI Research Diplomacy Team (FAIR) et al., 2022). Dafoe et al. (2020) set out a research agenda for cooperative AI.

#4.1 Expected utility

Given actions $a$, states of the world $s$ with probabilities $p(s)$, and a utility function $u(a, s)$ over outcomes, the expected utility of an action is

and a rational agent chooses $a^* = \arg\max_a EU(a)$. Von Neumann and Morgenstern (1944/2007) showed that if a preference relation over lotteries satisfies certain axioms (completeness, transitivity, continuity and independence), there is a utility function, unique up to positive affine transformation, whose expectation represents the preferences. The axioms are normative assumptions; they can be and are questioned (Ellsberg, 1961; Kahneman & Tversky, 1979).

#4.2 Sequential decisions

In a Markov decision process, an agent seeks a policy $\pi$ maximizing expected discounted return

This is the objective of reinforcement learning (TECH-RL-001 Reinforcement Learning).

#4.3 Normal-form games and equilibrium

A game specifies players, their strategy sets and payoff functions. A strategy profile is a Nash equilibrium if no player can improve their payoff by unilaterally changing strategy. Nash (1950) proved that every finite game has at least one equilibrium in mixed (randomized) strategies. A strategy is dominant if it is best regardless of others' choices.

The Prisoner's Dilemma illustrates a conflict between individual and collective rationality: mutual defection is the unique equilibrium of the one-shot game although mutual cooperation yields higher payoffs to both. In the repeated game, cooperative outcomes can be sustained, as studied by Axelrod and Hamilton (1981).

#4.4 Zero-sum games and minimax

In a two-player zero-sum game with payoff matrix $A$, von Neumann's minimax theorem states that

over mixed strategies $x, y$ (see von Neumann & Morgenstern, 1944/2007). This value can be computed by linear programming. The generative adversarial network objective is a two-player minimax game between a generator and a discriminator (Goodfellow et al., 2014), although training dynamics in practice need not converge to an equilibrium.

#4.5 Imperfect information and complexity

In games with hidden information, such as poker, players must reason about information sets, and the game tree is very large. Algorithms combining abstraction, equilibrium computation by iterative self-play, and real-time subgame solving were used in DeepStack (Moravčík et al., 2017) and Libratus (Brown & Sandholm, 2018). Daskalakis et al. (2009) showed that finding a Nash equilibrium is PPAD-complete, with the SICOMP abstract stating the result for three-player games; hardness of exact computation motivates the use of approximate or special-case methods. [VERIFICATION NEEDED: citation for the extension of PPAD-completeness to two-player games, not cited here]

#4.6 Cooperative inverse reinforcement learning

Hadfield-Menell et al. (2016) formalize value alignment as a cooperative game in which a human knows the reward function and a robot does not; the robot must infer it from the human's behaviour while both are rewarded by the human's reward. In that model, optimal behaviour includes the human teaching and the robot seeking clarification, in contrast to a robot that optimizes a fixed specified reward.

• Decision problems: under certainty, under risk (known probabilities), under uncertainty or ambiguity (unknown probabilities; Ellsberg, 1961).
• Normative versus descriptive theories: expected utility (normative) versus prospect theory (descriptive; Kahneman & Tversky, 1979).
• Games by structure: simultaneous versus sequential; zero-sum versus general-sum; perfect versus imperfect information; cooperative versus non-cooperative; one-shot versus repeated; two-player versus multi-player.
• Solution concepts: dominant strategy, Nash equilibrium, minimax value, and refinements (not covered in the sources cited here).
• Evolutionary game theory: strategies compete by relative success (Axelrod & Hamilton, 1981).
• Mechanism design: designing the rules of a game to induce desired behaviour (not covered by a source here).

• Game-playing AI. DeepStack and Libratus defeated professional players in heads-up no-limit Texas hold'em (Moravčík et al., 2017; Brown & Sandholm, 2018). Pluribus was reported to perform better than elite professionals in six-player no-limit hold'em over 10,000 hands (Brown & Sandholm, 2019). Cicero achieved more than double the average score of human players in 40 games of an anonymous online Diplomacy league and ranked in the top 10% of participants who played more than one game (Meta FAIR Diplomacy Team et al., 2022). These are results in specified games under specified conditions and do not demonstrate general strategic competence.
• Adversarial machine learning. The GAN objective (Goodfellow et al., 2014).
• Preference learning and alignment. Cooperative inverse reinforcement learning is a research formalization (Hadfield-Menell et al., 2016), not a deployed method.
• Multi-agent AI and governance. Cooperation problems among AI agents and among AI developers are framed in game-theoretic terms (Dafoe et al., 2020); competitive dynamics among developers is analysed in GOV-LAW-001 AI Governance and ECON-COMP-001 Compute Economics.

Strengths. Precise, mathematically developed models of choice and interaction; clear solution concepts; applicable to learning and planning algorithms.

Limitations.

• Descriptive failure. People systematically depart from expected-utility axioms (Ellsberg, 1961; Kahneman & Tversky, 1979).
• Computational intractability. Equilibrium computation is PPAD-hard (Daskalakis et al., 2009), and large games need approximation.
• Equilibrium selection. Games often have several equilibria, and theory does not always indicate which will be played.
• Utility specification. Utility or reward functions must be specified; mis-specified objectives lead to unintended behaviour. Neither the von Neumann-Morgenstern theorem nor the formalism supplies the content of the utility function.
• Idealization of agents. Real learning agents are not guaranteed to be expected-utility maximizers, and whether advanced AI systems will behave as such is an open question, not a result.

Open questions. How to model learning agents in games (convergence and equilibrium selection under learning); how to design agents that cooperate with humans and other agents in mixed-motive settings (Dafoe et al., 2020); and how to represent uncertain or evolving preferences (Hadfield-Menell et al., 2016).

As of 2026-10-15:

• The expected-utility representation theorem, the existence of Nash equilibria in finite games, and the PPAD-completeness of equilibrium computation are Established results.
• The claim that human decision-making deviates from expected utility is Well Supported empirically (Kahneman & Tversky, 1979; Ellsberg, 1961).
• The game-playing results cited are Well Supported as published demonstrations in their respective games; their scope is limited to those games.
• Whether advanced AI agents can be usefully modelled as expected-utility maximizers is Contested and bears on arguments in the safety literature; it is not asserted here.
• Cooperative AI as a research agenda (Dafoe et al., 2020) and the cooperative-game formulation of alignment (Hadfield-Menell et al., 2016) are Preliminary.

No registered forecast is made. Observed directions: multi-agent learning in mixed-motive games; evaluation of cooperation among language-model agents; and incorporation of preference uncertainty into agent design. Near-term work is likely to emphasize empirical evaluation in simulated games. Statements about long-term strategic dynamics among advanced AI systems and states are speculative scenarios and are treated in SAFE-XRISK-001 Existential Risk from AI.

• Foundational Concepts:
  • FOUND-008 Probability, Statistics and Bayesian Inference: probability in expected utility.
  • FOUND-002 Definitions of Intelligence: rationality as a definition.
• Related Methods & Technologies:
  • TECH-RL-001 Reinforcement Learning: sequential decision-making.
  • TECH-MARL-001 Multi-Agent Systems: interacting learning agents.
  • FOUND-006 Collective and Animal Intelligence: cooperation among agents in biology.
  • FOUND-010 Optimization and Gradient Descent: optimizing objectives, including minimax objectives.
• Advanced Implications & Future Trajectories:
  • SAFE-ALIGN-001 AI Alignment: objective specification.
  • GOV-LAW-001 AI Governance: strategic interaction among developers and states.