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)$)?

  • $\begingroup$ Since your database is finite (is it?) complexity won't be affected at all. $\endgroup$ – Raphael Sep 6 '17 at 1:51
  • $\begingroup$ @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? $\endgroup$ – rus9384 Sep 6 '17 at 1:54
  • $\begingroup$ What prevents me from storing all answers in the database, making the algorithm trivial (and O(1)-time)? $\endgroup$ – Raphael Sep 6 '17 at 5:40

You can say anything you want, if you define your terms and your notation and make it clear what you are saying.

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)$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.