<p>I am very confused, so this might not make sense. I am following the exposition in the polynomial hierarchy chapter of <a href="http://rads.stackoverflow.com/amzn/click/0201530821" rel="nofollow">Papadimitriou's textbook</a>.</p>

<p>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.</p>

<p>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 <em>assignment</em> 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}$?</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/0022000088900396" rel="nofollow">Krentel (1988, Thm 4.2)</a> 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) &lt; g(n)$ and $f(n) \le \frac12 \log n$.</p>

<p>(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.)</p>

CC BY-SA 3.0
2015-08-30T01:22:06.957Z
I think you are forgetting that reductions can blow up instance size.
Sasho Nikolov
CC BY-SA 3.0
2015-08-30T06:03:20.037Z
@SashoNikolov: Thanks, that makes sense. So suppose $0 < s < t$ and $f \in FP^{NP}[n^t]$, then we can reduce $f$ to some $g\in FP^{NP}[n^s]$ just by adding $n^{t/s}$ new symbols to the input. This doesn't seem to imply $f\in FP^{NP}[n^s]$, though, so that these classes appear not to be closed under reductions, so that being complete for them makes no sense. Agreed?
Dominik Peters
CC BY-SA 3.0
2015-08-30T10:28:28.497Z
I think what Sasho points out is that "... which suggests that $FP^{NP[n^2]}=FP^{NP}$" is wrong. It seems perfectly plausible that $FP^{NP[n^c]}\ne FP^{NP}$ for all c.
Emil Jeřábek
CC BY-SA 3.0
2015-08-30T10:56:51.210Z
being complete (under polytime reductions) for $FP^{NP}$ makes sense, but not $FP^{NP[n^2]}$ which is not closed under polytime  reductions.
Sasho Nikolov
<cc.complexity-theory><separation>
When is $FP^{NP[f(n)]}$ the same as $FP^{NP}$?
Dominik Peters
# When is $FP^{NP[f(n)]}$ the same as $FP^{NP}$?

(Asked by: username_0 on 2015-08-29)

I am very confused, so this might not make sense. I am following the exposition in the polynomial hierarchy chapter of [Papadimitriou's textbook](http://rads.stackoverflow.com/amzn/click/0201530821).

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)](http://www.sciencedirect.com/science/article/pii/0022000088900396) 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.)

**Tags:** cc.complexity-theory, separation
> **Comments:**
> **username_1**: I think you are forgetting that reductions can blow up instance size.  
> **username_0**: @SashoNikolov: Thanks, that makes sense. So suppose $0 < s < t$ and $f \in FP^{NP}[n^t]$, then we can reduce $f$ to some $g\in FP^{NP}[n^s]$ just by adding $n^{t/s}$ new symbols to the input. This doesn't seem to imply $f\in FP^{NP}[n^s]$, though, so that these classes appear not to be closed under reductions, so that being complete for them makes no sense. Agreed?  
> **username_2**: I think what Sasho points out is that "... which suggests that $FP^{NP[n^2]}=FP^{NP}$" is wrong. It seems perfectly plausible that $FP^{NP[n^c]}\ne FP^{NP}$ for all c.  
> **username_1**: being complete (under polytime reductions) for $FP^{NP}$ makes sense, but not $FP^{NP[n^2]}$ which is not closed under polytime  reductions.  

---

## 0 answers

