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

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


Your Answer

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