NP problem that has a verifier that uses $\leq 3 \log_2 n$ bits of memory, how does that influence the complexity of the problem itself?

Question

Translated exercise:

Algorithms, that solve NP problems. Let's assume a problem $R$ is in the set $\sf NP$. A verifier $M(x,y)$ for this problem works in time $O(n)$ and uses extra information $y$, which is is $\leq 3 \log n$ bits. What $f(n)$ can we say, that $R$ belongs to in ${\sf TIME}(f(n))$?

---

The only part I dont get is how a verifier using some (very small) extra memory would influence the problem $R$ beloging to a specific ${\sf TIME}(f(n))$ class. Please just point me in the right direction.

Any Wikipedia link or a single sentence. My book got nothing.

What does "extra information $y$, which is is $\leq 3 \log n$ bits" even mean?

Answer 1

tl;dr: the keyword is enumeration. That is, you know that for any $x$, if there is a witness $y$ proving $x\in {\sf R}$ then it is small, so you can afford to try out all possible witnesses.

Stop reading here is you only wanted a clue.

---

Outline: What it means is that the problem $R\in\sf NP$ satisfies the following. There exists an algorithm $M$ such that for any $x$ of size $\lvert x\rvert = n$:

• if $x\in R$, there there exists $y\in\{0,1\}^\ast$ with $\lvert y\rvert \leq 3\log_2 n$ such that $M(x,y)=1$;

• if $x\notin R$, there for any $y\in\{0,1\}^\ast$ (in particular with $\lvert y\rvert \leq 3\log_2 n$) we have $M(x,y)=0$.

Moreover, $M$ runs in time $O(n)$, when given inputs $x,y$ with $\lvert x\rvert = n$.

Now, why does the assumption that the certificate $y$ is small help? Well, here is the idea:

Given an input $x$ of size $n$, how much time does it take to try all possible $y\in\{0,1\}^\ast$ such that $\lvert y\rvert \leq 3\log_2 n$?

More detail: (spoilers)

The answer is $O(n^3)$, since there are $$ \sum_{k=0}^{3\log_2 n} 2^k = \frac{2^{3\log_2 n+1}-1}{2-1} = 2^{3\log_2 n+1}-1 = \frac{n^3}{2}-1 $$ such "candidates" $y$.

So given $M$ as above, on input $x$ of size $n$ once can iterate over all possible witnesses $y$ of size at most $3\log_2 n$, and compute $M(x,y)$ for each of them.

• If there exists $y^\ast$ such that $M(x,y^\ast)=1$, return $\sf accept$;
• If there is no $y$ such that $M(x,y)=1$, return $\sf reject$

and the loop overall takes time $O(n^3)\cdot O(n) = O(n^4)$ (checking $O(n^3)$ possibilities, with $O(n)$ computation for each.)