NP problem in $\mathit{TIME}(f(n))$

Question

This is a task in Algorithm theory course I cannot wrap my head around.

Assume a problem $ R \in \mathit{NP} $ can be solved with $M(x,y)$ and it solves in $O(n^3)$ with additional information $y$ which is no longer than $3\log n$ bits.

Question: For what function $f(n)$ we can say that $R \in \mathit{TIME}(f(n))$?

I'm thinking it's $n^3$ but is seems too easy. But if it is right… why?

Answer 1

Hint: If you know the size of the certificate, then the standard simulation argument is to enumerate over all possible certificates and try them. So:

• How many certificates do you have?
• What is the runtime to try a single certificate?

Answering these two questions will give you your bound. Note that the bound is not $O(n^3)$ runtime.