0
$\begingroup$

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

a binary tree representing the computation tree

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.