91Ó°ÊÓ

A nondeterministic turning machine assigns a problem to the NP (nondeterministic polynomial time) class if it can be solved in polynomial time.

Let A be the unary NP complete language that satisfies the condition $\mathrm{ϕ}∈SAT⇔1^{f\left(\mathrm{ϕ}\right)}∈A$. The formula for calculating $1^{f\left(\mathrm{ϕ}\right)}$the amount of time required is $p\left|\mathrm{ϕ}\right|$. Let $T=\left(V,E\right)$be a satisfiable call tree for an input formula. For example $v∈V$, consider $\mathrm{ϕ}$be the V formula with an argument.

Consider two nodes $v,v\text{'}$neither of which is an ancestor of the other. At the time of the v' call, it is known whether $p\left|\mathrm{ϕ}\right|$is satisfiable, therefore the hashmap is defined for $f\left({\mathrm{ϕ}}_v\right)$ . As a result $f\left({\mathrm{ϕ}}_v\right)=f\left({\mathrm{ϕ}}_{v\text{'}}\right)$ . There are at most n nodes on any such path., and there are at most $n.p\left(\right|\mathrm{ϕ}\left|\right)≤\left|\mathrm{ϕ}\right|.p\left(\right|\mathrm{ϕ}\left|\right)$ nodes on any $f\left({\mathrm{ϕ}}_v\right)≤p\left(\right|\mathrm{ϕ}\left|\right)$ for all $v∈V$.