I am very confused, so this might not make sense. I am following the exposition in the polynomial hierarchy chapter of Papadimitriou's textbook.We are in the function-problem world. The problem CLIQUE-SIZE given a graph, find the size of its maximum clique is not thought to be $FP^{NP}$-complete since it can be solved by logarithmically many calls to an NP-oracle through binary search. This puts CLIQUE-SIZE in $FP^{NP[\log(n)]}$, and the problem is known to be complete for this class.On the other hand, MAX-WEIGHTED-SAT is known to be $FP^{NP}$-complete. This is the problem given a CNF-formula with binary clause weights, find an assignment maximising the weight of satisfied clauses. Now we seem to be able to solve this question in $O(n^2)$ calls to an NP-oracle, where $n$ is the input size. (See below for why I think this). Hence this problem is in $FP^{NP[n^2]}$, which suggests that $FP^{NP[n^2]} = FP^{NP}$. Is that right? If so, for which (nice) functions $f(n)$ do we have $FP^{NP[f(n)]} = FP^{NP}$?Krentel (1988, Thm 4.2) shows that (unless $P=NP$) we have $FP^{NP[f(n)]} \subsetneq FP^{NP[g(n)]}$ when $f$ and $g$ are smooth with $f(n) < g(n)$ and $f(n) \le \frac12 \log n$.(To find a max-assignment in $O(n^2)$ queries: the maximum possible objective value is the sum of all weights. The logarithm of this value is $O(n)$, since all the digits of the individual weights are part of the input. Hence by binary search we can in $O(n)$ calls to an NP MAX-WEIGHTED-SAT $\ge k$-oracle find the maximum possible weight. Now go through the $O(n)$ variables in the formula one-by-one, set them false, and check whether this decreased the possible objective value. If so, set it true, otherwise leave it false. Go to the next variable. This takes $O(n^2)$ calls.)
When is $FP^{NP[f(n)]}$ the same as $FP^{NP}$?
cc.complexity theory;separation