# If we allow a database, what complexity class it is?

Let we have some problem $A$. Input length is $n$. Now we write a database that will store info about some positive instances of problem $A$. For every $n$ size of $n^{th}$ sector of DB is $O(f(n))$. $f(n)$ is some function.

Then we assume that some solver for problem in complexity class $C$ (for example, $GI$) can use this DB to solve the problem $A$. Can we say that $A\in C/f(n)$ ($C$ solver with advice of size $f(n)$)?

• Since your database is finite (is it?) complexity won't be affected at all.
– Raphael
Sep 6, 2017 at 1:51
• @Raphael, we assume (in practice it is impossible, of course) that there exist a database that is infinite. But it is divided into sectors. Each sector contains info about some particular $n$ and has size $O(f(n))$ as I wrote in the question. Does it count as advice string? Sep 6, 2017 at 1:54
• What prevents me from storing all answers in the database, making the algorithm trivial (and O(1)-time)?
– Raphael
Sep 6, 2017 at 5:40

In this case I would not expect someone to know what you mean by $M/f(n)$ or by $A \in M/f(n)$. Something like $P/\text{poly}$ is well-understood, but $P$ is a complexity class, and $M$ is a specific machine. Rather than risking confusion, just say what you mean -- it only takes a sentence to say that the problem can be decided by $M$ using advice of size $f(n)$.