# Complexity of $FP^{NP[O(n)]}$ with advice string?

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

• They belong to $\mathrm{FP^{NP}\!\!/log}$, by definition. What else do you expect to hear? – Emil Jeřábek 3.0 Jul 10 '17 at 16:38
• 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 Jul 10 '17 at 16:46
• 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 3.0 Jul 10 '17 at 16:50
• 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 Jul 10 '17 at 17:21
• @EmilJeřábek He is asking whether we can reduce the number of oracle calls if we have log size advice bits – T.... Jul 10 '17 at 19:03