For each problem \(X\), it is also assumed that an appropriate notion of problem size is defined for its instances. Formally, this is a function \(\lvert\cdot \rvert: X \rightarrow \mathbb{N}\) chosen so that the efficiency of a decision algorithm for \(X\) will varying uniformly in \(\lvert x\rvert\). As we have seen, if \(X \subseteq \mathbb{N}\), it is standard to take \(\lvert n\rvert = \log_2(n)\) – i.e. the number of digits (or length) of the binary numeral \(\ulcorner n \urcorner\) representing \(n\). Similarly if \(X\) is a class of logical formulas over a language \(\mathcal{L}\) (e.g. that or propositional or first-order logic), then \(\lvert\phi\rvert\) will typically be a measure of \(\phi\)’s syntactic complexity (e.g. the number of propositional variables or clauses it contains). If \(X\) is a graph theoretic problem its instances will consist of the encodings of finite graphs of the form \(G = \langle V,E \rangle\) where \(V\) is a set of vertices and \(E \subseteq V \times V\) is a set of edges. In this case \(\lvert G\rvert\) will typically be a function of the cardinalities of the sets \(V\) and \(E\).