> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/theoretical.md).

# theoretical

## Basic idea

Mathematical foundations of computation: complexity, computability, constructive logic and proof theory, descriptive measures (Kolmogorov complexity), and structural tools (space-filling curves) used by theoreticians and systems folks alike.

## Key formulas

* Kolmogorov complexity: $K(x) = \min{|p| : U(p) = x}$
* Universal prior (Solomonoff): $M(x) = \sum\_{p : U(p)=x\*} 2^{-|p|}$
* Cook–Levin: $\mathrm{SAT} \in \mathrm{NP}$ and $\forall L \in \mathrm{NP},\ L \leq\_p \mathrm{SAT}$
* Intuitionistic negation: $\neg P := P \to \bot$
* Big-O: $f = O(g) \iff \exists c, n\_0.\ f(n) \le c g(n)$ for $n \ge n\_0$
* Rice: every non-trivial semantic property of partial computable functions is undecidable.
* Savitch: $\mathrm{NSPACE}(f(n))\subseteq\mathrm{SPACE}(f(n)^2)$.
* Master theorem compares $f(n)$ in $T(n)=aT(n/b)+f(n)$ with $n^{\log\_ba}$.
* Cut elimination removes intermediate lemmas from sequent proofs; incompleteness limits what arithmetic theories can prove.
* Kripke frames interpret modal accessibility and intuitionistic growth of information.
* Linear logic tracks assumptions as resources; proof nets expose the dependency structure of proofs.
* Skolemization replaces existential witnesses with fresh functions while preserving satisfiability.
* Gödel completeness equates first-order semantic consequence with formal provability.
* Assuming $P\ne NP$, Ladner's theorem guarantees NP-intermediate languages.