In the context of P/poly complexity class, an advice function is mentioned.
How is the advice function different than an oracle(/certificate)?
https://en.wikipedia.org/wiki/Advice_(complexity) https://en.wikipedia.org/wiki/P/poly
$\begingroup$
$\endgroup$
3
-
$\begingroup$ For any input length $n$ there is advice $A(n)$. Then $A(n)$ is the certificate for any string of a length $n$ from the language. If $A(n)$ doesn't work for a string of length $n$, the string is not in the language. $\endgroup$– user114966Mar 14, 2021 at 1:28
-
$\begingroup$ @Dmitry, thanks for the comment, but sorry... I don't understand how exactly it answers my questions... Could you please clarify a bit more? Basically I'm just trying to know if an oracle and "advice" are synonyms for the same things, or if they're different that what is exactly the difference. AFAIK, both are some sort of "magic"/"cheat" that can help by answering a question. an oracle always answers true/false, but I just noticed the advice function may output a string, so is that the difference, similar concept different output type? $\endgroup$– user206904Mar 14, 2021 at 2:28
-
1$\begingroup$ I see, I thought you confuses advice and certificate. No, they are not synonyms. Advice is a string with the property I've described. Oracle, like you said, is a magic function which can solve a specific problem. I.e. we say that a TM has access to an oracle for problem $X$ when it has a special (oracle) tape such that, when we reach a certain TM state, the contents of the tape are treated as input for $X$, and then they are replaced with the corresponding output of $X$. You can say that $P/poly$ is a class of languages solvable in poly-time with the following oracle: given $n$, return $A(n)$ $\endgroup$– user114966Mar 14, 2021 at 2:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No, they are not the same. An oracle is something that an algorithm can send inputs to, and get back outputs, possibly many times. Advice is a single value that is provided to the algorithm, and depends only on the length of the input to the algorithm.
