1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ Since your database is finite (is it?) complexity won't be affected at all. $\endgroup$
    – Raphael ♦
    Sep 6, 2017 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, 2017 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, 2017 at 5:40

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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