<p>$FP^{NP[O(n)]}$ is the functional complexity class with $O(n)$ queries to an $NP$ oracle.</p>

<p>Are there any interesting classes $\mathcal C$ such that
$$FP^{NP[O(n)]}\subseteq\mathcal C/\log$$
besides $FP^{NP[O(n)]}$ itself? 
In particular, can we show that $FP^{NP[O(n)]}\subseteq FP^{NP[f(n)]}/\log$ for some $f(n) = o(n)$?</p>

CC BY-SA 3.0
2017-07-10T16:38:22.357Z
They belong to $\mathrm{FP^{NP}\!\!/log}$, by definition. What else do you expect to hear?
Emil Jeřábek
CC BY-SA 3.0
2017-07-10T16:46:09.300Z
Thanks. my query was regarding the number of Oracle calls required for the new problem (assuming the advise string). I am not conversant in this notation (haven't seen one above), I am assuming this is equivalent to $FP^{NP[log]}$ oracle calls given the advise string.
J.Doe
CC BY-SA 3.0
2017-07-10T16:50:29.197Z
No. “/log” means “with logarithmic advice”. There is no restriction on the number of oracle calls, as there wasn’t one in $\mathrm{FP^{NP}}$ to begin with. I am more and more at loss to understand what is it that you are trying to ask.
Emil Jeřábek
CC BY-SA 3.0
2017-07-10T17:21:22.413Z
Ok. My mistake. I thought the notation $FP^{NP}$ implicitly had the linear number of calls restriction (thus I mentioned in the query above). So, to clarify I am looking how a log sized advise string would affect the problem's calls where original problem had a linear number of $NP$ query restrictions.
J.Doe
CC BY-SA 3.0
2017-07-10T17:27:06.493Z
I still have no idea what you are asking. Clearly, if you take an oracle machine making $x$ oracle calls, and supply it with an advice, it will still make the exact same number of calls.
Emil Jeřábek
CC BY-SA 3.0
2017-07-10T17:30:34.150Z
Umm I have my doubts, I think depending on the advise the number of calls can be reduced to solve the same problems.
J.Doe
CC BY-SA 3.0
2017-07-10T19:03:13.827Z
@EmilJeřábek He is asking whether we can reduce the number of oracle calls if we have log size advice bits
Turbo
CC BY-SA 3.0
2017-07-11T08:22:42.500Z
Is he? Well then, that's not what is written in the question at all.
Emil Jeřábek
CC BY-SA 3.0
2017-07-11T08:27:08.870Z
as pointed out i was asking the same. I tried to convey it in the comments too but couldn't get it across.
J.Doe
<cc.complexity-theory><oracles><advice-and-nonuniformity>
Complexity of $FP^{NP[O(n)]}$ with advice string?
J.Doe
# Complexity of $FP^{NP[O(n)]}$ with advice string?

(Asked by: username_0 on 2017-07-10)

$FP^{NP[O(n)]}$ is the functional complexity class with $O(n)$ queries to an $NP$ oracle.

Are there any interesting classes $\mathcal C$ such that
$$FP^{NP[O(n)]}\subseteq\mathcal C/\log$$
besides $FP^{NP[O(n)]}$ itself?
In particular, can we show that $FP^{NP[O(n)]}\subseteq FP^{NP[f(n)]}/\log$ for some $f(n) = o(n)$?

**Tags:** cc.complexity-theory, oracles, advice-and-nonuniformity
> **Comments:**
> **username_1**: They belong to $\mathrm{FP^{NP}\!\!/log}$, by definition. What else do you expect to hear?  
> **username_0**: Thanks. my query was regarding the number of Oracle calls required for the new problem (assuming the advise string). I am not conversant in this notation (haven't seen one above), I am assuming this is equivalent to $FP^{NP[log]}$ oracle calls given the advise string.  
> **username_1**: No. “/log” means “with logarithmic advice”. There is no restriction on the number of oracle calls, as there wasn’t one in $\mathrm{FP^{NP}}$ to begin with. I am more and more at loss to understand what is it that you are trying to ask.  
> **username_0**: Ok. My mistake. I thought the notation $FP^{NP}$ implicitly had the linear number of calls restriction (thus I mentioned in the query above). So, to clarify I am looking how a log sized advise string would affect the problem's calls where original problem had a linear number of $NP$ query restrictions.  
> **username_1**: I still have no idea what you are asking. Clearly, if you take an oracle machine making $x$ oracle calls, and supply it with an advice, it will still make the exact same number of calls.  
> **username_0**: Umm I have my doubts, I think depending on the advise the number of calls can be reduced to solve the same problems.  
> **username_2**: @EmilJeřábek He is asking whether we can reduce the number of oracle calls if we have log size advice bits  
> **username_1**: Is he? Well then, that's not what is written in the question at all.  
> **username_0**: as pointed out i was asking the same. I tried to convey it in the comments too but couldn't get it across.  

---

## 0 answers

