P ⊆ P/poly

Inclusion · folklore

Statement

P $\subseteq$ poly — folklore.

Sketch

The tableau simulation turns a Turing machine running in time $t(n)$ into a circuit of size $O(t(n{)}^2)$ for each input length $n$, so a polynomial-time decider yields a polynomial-size circuit family; in the advice formulation, empty advice suffices.