# How to explain that a program that runs in NTIME(O(lg n)) is in the class P?

if a non-deterministic program executes only lg(n) decisions on each branch of the computation tree, then the problem this program solves is in P? That means, there is a deterministic algorithm that computes the solution in a polynomial time.

The answer yes looks intuitive to me when I'm looking the tree, but I don't know how to actually "proof" that

• One idea is $2^{C\log n} = n^C$. – Yuval Filmus Nov 8 '20 at 0:05