The time complexity \(t_N(n)\) of a non-deterministic machine \(N\) is the maximum of the depths of the computation trees \(\mathcal{T}^N_{C_0(x)}\) for all inputs \(x\) such that \(\lvert x\rvert = n\). Relative to this definition, non-deterministic machines can be used to implement many brute force algorithms in time polynomial in \(n\). For instance the \(\sc{SAT}\) problem can be solved by a non-deterministic machine which on input \(\phi\) uses part of its tape to non-deterministically construct (or ‘guess’) a string representing a valuation \(v\) assigning a truth value to each of \(\phi\)’s \(n\) propositional variables and then computes \(\llbracket \phi \rrbracket_v\) using the method of truth tables (which is polynomial in \(n\)). As \(\phi \in \sc{SAT}\) just in case a satisfying valuation exists, this is a correct method for deciding \(\sc{SAT}\) relative to conventions (i)–(iii) from above. This means that \(\sc{SAT}\) can be solved in polynomial time relative to \(\mathfrak{N}\).