<p>$\let\mr\mathrm$Let me denote the problem as $S$. Gottlob and Fermüller state that if $S$ is solvable in $\mr{FP}^{\mr{SAT}[\log n]}$, then $\mr{P}=\mr{NP}$. However, the argument actually shows more generally that if $S$ is in $\mr{FP}^{\mr{SAT}[q(n)]}$, then SAT is solvable in time $\mr{poly}(n2^{q(n)})$. In particular, assuming the exponential time hypothesis, $S$ cannot be solved with a sublinear number of $\mr{NP}$ queries.</p>

<p>On the other hand, $S$ shouldn’t be hard for $\mr{FP}^\mr{SAT}$—or even $\mr{FP}^{\mr{SAT}[2]}$—under many-one search-problem reductions. For definiteness, let me assume (following Gottlob and Fermüller) that $S$ is formulated as a total search problem, required to answer “unsatisfiable” for unsatisfiable formulas. Let $L$ be a language whose $\{0,1\}$-valued characteristic function $f_L$ is reducible to $S$, that is, there are poly-time functions $g,h$ such that
$$S(g(x),y)\implies f_L(x)=h(x,y).$$
Then
\begin{align}
x\in L\iff{}&amp;\bigl(g(x)\in\mr{UNSAT}\land h(x,\text{‘unsat’})=1\bigr)\\
&amp;\lor\exists y\,\bigl(y\text{ satisfies }g(x)\land h(x,y)=1\bigr),
\end{align}
and we have a similar expression for $\overline L$ with $0$ in place of $1$, hence
$$L\in\mr{DP}\cap\mr{coDP}.$$
If this were true for all $\mr{DP}$ languages $L$, then the Boolean hierarchy would collapse to $\mr{DP}$, hence the polynomial hierarchy would collapse to something similar one level up. So, assuming no such collapse takes place, there are $\mr{FP}^{\mr{SAT}[2]}$ functions (in fact, characteristic functions of $\mr{DP}$ predicates) not reducible to $S$.</p>

<p>Note that if we instead formulate $S$ so that it is <em>undefined</em> on unsatisfiable inputs, it only becomes easier; it is a (non-total) $\mr{FNP}$ problem. Then it is not hard to see that $f_L$ is reducible to $S$ only if $L\in\mr{NP}\cap\mr{coNP}$. In particular, $S$ is not hard for $\mr{FP}^{\mr{SAT}[1]}$ (or characteristic functions of $\mr{NP}$ languages) unless $\mr{NP}=\mr{coNP}$.</p>

CC BY-SA 3.0
2015-05-12T18:50:08.163Z
Thank you a lot for this detailed answer. Since I'm not too deep into complexity theory, it will take me some time to fully understand your answer. Let me start by asking what your notations of FP^SAT and FP^SAT[2] mean? Is FP^SAT[q(n)] = FP^SAT?
John Threepwood
CC BY-SA 3.0
2015-05-12T18:57:36.123Z
If $A$ is an oracle, and $q(n)$ an integer function, $\mr{FP}^{A[q(n)]}$ denotes the class of problems solvable by a polynomial-time algorithm allowed to make $q(n)$ queries to $A$ (where $n$ is the input length). So, $\mr{FP}^{\mr{SAT}}=\mr{FP}^{\mr{SAT}[\mr{poly}(n)]}$ as the machine cannot make more than polynomially many queries anyway, but if $q(n)$ is a slower growing function (such as $\log n$ or a constant), the class may get smaller.
Emil Jeřábek
CC BY-SA 3.0
2015-05-12T19:08:33.357Z
Whether you put NP or SAT in the superscript makes no difference.
Emil Jeřábek
CC BY-SA 3.0
2015-05-12T19:12:05.207Z
I really appreciate your help, thank you. So $\mathrm{FP}^{SAT[2]}$ is the class of problems solvable in polynomial time with exactly 2 calls to a SAT oracle?
John Threepwood
CC BY-SA 3.0
2015-05-12T19:15:17.783Z
The class of problems computable in polynomial time with 2 calls to a SAT oracle. They do not all necessarily *require* 2 calls; if they can get away with less, good for them.
Emil Jeřábek
CC BY-SA 3.0
2015-05-12T19:27:36.640Z
Thank you again. As far as I could understand from your first paragraph: If the exponential time hypothesis is true (which we do not know yet), then $S$ cannot be solved with a sublinear number of $SAT$ queries and therefore, $S$ would be $FP^{SAT}$-hard? Is this conclusion correct?
John Threepwood
CC BY-SA 3.0
2015-05-12T20:03:53.840Z
No. “X is Y-hard” means that every problem from Y is reducible to X, which is a much stronger requirement than just X not being computable in a version of Y with smaller resource bounds. For example, while the exponential-time hypothesis postulates that SAT is not computable in subexponential time, this doesn’t imply that SAT is EXP-complete (likely it isn’t).
Emil Jeřábek
CC BY-SA 3.0
2015-05-12T20:18:55.640Z
Thank for clarification. I already feel uncomfortable asking so many questions and stress your time. Now I understand your first paragraph. But I have trouble to overcome the first sentence of the second. This is likely because I do not understand what is meant by 'many-one search-problem reductions'. I just could find many-to-one reductions in the context of decision problems. Why should $S$ not be in $FP^{SAT[2]}$-hard when we already know that a logarithmic number of SAT calls is not sufficient unless $P = NP$? Doesn't follow from Gottlob/Fermüller that $S$ is $FP^{SAT[log n]}$-hard?
John Threepwood
CC BY-SA 3.0
2015-05-12T20:58:01.283Z
Didn’t I just answer that? First make sure you really understand my last comment. Only then worry about what is the appropriate notion of reduction in this context, that’s a secondary issue.
Emil Jeřábek
CC BY-SA 3.0
2015-05-13T06:15:47.423Z
Okay, I had an error in reasoning: To show that $S$ is $Y$-hard it would need another problem which already is $Y$-hard and can be reduced to $S$ (which means that every $Y$-hard problem can be solved by a reduction to $S$). But $S$ *felt* like it must be hard to solve when even a logarithmic number of SAT-oracle calls was not sufficient. But you say it should not be $FP^{SAT[2]}$-hard (meaning no $FP^{SAT[2]}$-hard problem can be reduced to $S$). This feels somehow strange intuitively spoken. Can this be explained?
John Threepwood
CC BY-SA 3.0
2015-05-13T11:00:26.887Z
Well, this just means that the number of NP oracle queries is not an exhaustive gauge of the intrinsic complexity of this particular problem, just like deterministic running time is not a very illuminative measure for NP-complete problems. There is no reason to expect that if a problem appears in an arbitrarily chosen hierarchy, it should be complete for one of its levels.
Emil Jeřábek
CC BY-SA 3.0
2015-05-13T11:20:32.310Z
I see, I had another error in reasoning: I somehow I thought every problem has to be complete for some level of SAT-oracle calls. But as you said, this must not be the case. Thank you a lot for your help that helped me understand things much better.
John Threepwood
CC BY-SA 3.0
2015-05-13T17:55:16.780Z
One more question: In your first paragraph, is $q(n)$ a polylogarithmic function (as it is in Gottlob/Fermüller) or a polynom?
John Threepwood
CC BY-SA 3.0
2015-05-13T21:05:04.657Z
It can be *any* function (though it only makes good sense if it is at most polynomial).
Emil Jeřábek
CC BY-SA 3.0
2015-05-12T17:29:59.757Z
2015-05-12T17:54:33.157Z
2015-05-12T17:54:33.157Z
Emil Jeřábek
<p>By the well-known <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Self-reducibility">self-reducibility of SAT</a> we can obtain a satisfying variable assignment for a Boolean formula by a polynomial number of calls to an $NP$ oracle (delivering only yes/no answers). Thus, the computation of a satisfying variable assignment for a Boolean formula is in $FP^{NP}$.</p>

<p>On the other hand, it is not possible with only a logarithmic number of $NP$ queries to obtain a satisfying variable assignment of Boolean formula as shown by <a href="http://www.sciencedirect.com/science/article/pii/000437029390069N">Gottlob and Fermüller</a>.</p>

<p><strong>Has it already been shown that the computation of a satisfying variable assignment is also $FP^{NP}$-hard?</strong></p>

CC BY-SA 3.0
2015-05-12T13:41:41.293Z
Rupei Xu, I made some edits to clarify that I am looking for a satisfying variable assignment (no counting or optimization here, just any variable assignment which satisfies the Boolean formula). If it is still unclear, please let me know.
John Threepwood
<sat><complexity>
Is the computation of a satisfying variable assignment for a Boolean formula $FP^{NP}$-hard?
John Threepwood
# Is the computation of a satisfying variable assignment for a Boolean formula $FP^{NP}$-hard?

(Asked by: username_0 on 2015-05-12)

By the well-known [self-reducibility of SAT](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Self-reducibility) we can obtain a satisfying variable assignment for a Boolean formula by a polynomial number of calls to an $NP$ oracle (delivering only yes/no answers). Thus, the computation of a satisfying variable assignment for a Boolean formula is in $FP^{NP}$.

On the other hand, it is not possible with only a logarithmic number of $NP$ queries to obtain a satisfying variable assignment of Boolean formula as shown by [Gottlob and Fermüller](http://www.sciencedirect.com/science/article/pii/000437029390069N).

**Has it already been shown that the computation of a satisfying variable assignment is also $FP^{NP}$-hard?**

**Tags:** sat, complexity
> **Comments:**
> **username_0**: Rupei Xu, I made some edits to clarify that I am looking for a satisfying variable assignment (no counting or optimization here, just any variable assignment which satisfies the Boolean formula). If it is still unclear, please let me know.  

---

## 1 answers

### Answer by username_1 on 2015-05-12. Score: 8 | Accepted answer

$\let\mr\mathrm$Let me denote the problem as $S$. Gottlob and Fermüller state that if $S$ is solvable in $\mr{FP}^{\mr{SAT}[\log n]}$, then $\mr{P}=\mr{NP}$. However, the argument actually shows more generally that if $S$ is in $\mr{FP}^{\mr{SAT}[q(n)]}$, then SAT is solvable in time $\mr{poly}(n2^{q(n)})$. In particular, assuming the exponential time hypothesis, $S$ cannot be solved with a sublinear number of $\mr{NP}$ queries.

On the other hand, $S$ shouldn’t be hard for $\mr{FP}^\mr{SAT}$—or even $\mr{FP}^{\mr{SAT}[2]}$—under many-one search-problem reductions. For definiteness, let me assume (following Gottlob and Fermüller) that $S$ is formulated as a total search problem, required to answer “unsatisfiable” for unsatisfiable formulas. Let $L$ be a language whose $\{0,1\}$-valued characteristic function $f\_L$ is reducible to $S$, that is, there are poly-time functions $g,h$ such that
$$S(g(x),y)\implies f\_L(x)=h(x,y).$$
Then
\begin{align}
x\in L\iff{}&\bigl(g(x)\in\mr{UNSAT}\land h(x,\text{‘unsat’})=1\bigr)\\
&\lor\exists y\,\bigl(y\text{ satisfies }g(x)\land h(x,y)=1\bigr),
\end{align}
and we have a similar expression for $\overline L$ with $0$ in place of $1$, hence
$$L\in\mr{DP}\cap\mr{coDP}.$$
If this were true for all $\mr{DP}$ languages $L$, then the Boolean hierarchy would collapse to $\mr{DP}$, hence the polynomial hierarchy would collapse to something similar one level up. So, assuming no such collapse takes place, there are $\mr{FP}^{\mr{SAT}[2]}$ functions (in fact, characteristic functions of $\mr{DP}$ predicates) not reducible to $S$.

Note that if we instead formulate $S$ so that it is *undefined* on unsatisfiable inputs, it only becomes easier; it is a (non-total) $\mr{FNP}$ problem. Then it is not hard to see that $f\_L$ is reducible to $S$ only if $L\in\mr{NP}\cap\mr{coNP}$. In particular, $S$ is not hard for $\mr{FP}^{\mr{SAT}[1]}$ (or characteristic functions of $\mr{NP}$ languages) unless $\mr{NP}=\mr{coNP}$.

> **Comments:**
> **username_0**: Thank you a lot for this detailed answer. Since I'm not too deep into complexity theory, it will take me some time to fully understand your answer. Let me start by asking what your notations of FP^SAT and FP^SAT[2] mean? Is FP^SAT[q(n)] = FP^SAT?  
> **username_1**: If $A$ is an oracle, and $q(n)$ an integer function, $\mr{FP}^{A[q(n)]}$ denotes the class of problems solvable by a polynomial-time algorithm allowed to make $q(n)$ queries to $A$ (where $n$ is the input length). So, $\mr{FP}^{\mr{SAT}}=\mr{FP}^{\mr{SAT}[\mr{poly}(n)]}$ as the machine cannot make more than polynomially many queries anyway, but if $q(n)$ is a slower growing function (such as $\log n$ or a constant), the class may get smaller.  
> **username_1**: Whether you put NP or SAT in the superscript makes no difference.  
> **username_0**: I really appreciate your help, thank you. So $\mathrm{FP}^{SAT[2]}$ is the class of problems solvable in polynomial time with exactly 2 calls to a SAT oracle?  
> **username_1**: The class of problems computable in polynomial time with 2 calls to a SAT oracle. They do not all necessarily *require* 2 calls; if they can get away with less, good for them.  
> **username_0**: Thank you again. As far as I could understand from your first paragraph: If the exponential time hypothesis is true (which we do not know yet), then $S$ cannot be solved with a sublinear number of $SAT$ queries and therefore, $S$ would be $FP^{SAT}$-hard? Is this conclusion correct?  
> **username_1**: No. “X is Y-hard” means that every problem from Y is reducible to X, which is a much stronger requirement than just X not being computable in a version of Y with smaller resource bounds. For example, while the exponential-time hypothesis postulates that SAT is not computable in subexponential time, this doesn’t imply that SAT is EXP-complete (likely it isn’t).  
> **username_0**: Thank for clarification. I already feel uncomfortable asking so many questions and stress your time. Now I understand your first paragraph. But I have trouble to overcome the first sentence of the second. This is likely because I do not understand what is meant by 'many-one search-problem reductions'. I just could find many-to-one reductions in the context of decision problems. Why should $S$ not be in $FP^{SAT[2]}$-hard when we already know that a logarithmic number of SAT calls is not sufficient unless $P = NP$? Doesn't follow from Gottlob/Fermüller that $S$ is $FP^{SAT[log n]}$-hard?  
> **username_1**: Didn’t I just answer that? First make sure you really understand my last comment. Only then worry about what is the appropriate notion of reduction in this context, that’s a secondary issue.  
> **username_0**: Okay, I had an error in reasoning: To show that $S$ is $Y$-hard it would need another problem which already is $Y$-hard and can be reduced to $S$ (which means that every $Y$-hard problem can be solved by a reduction to $S$). But $S$ *felt* like it must be hard to solve when even a logarithmic number of SAT-oracle calls was not sufficient. But you say it should not be $FP^{SAT[2]}$-hard (meaning no $FP^{SAT[2]}$-hard problem can be reduced to $S$). This feels somehow strange intuitively spoken. Can this be explained?  
> **username_1**: Well, this just means that the number of NP oracle queries is not an exhaustive gauge of the intrinsic complexity of this particular problem, just like deterministic running time is not a very illuminative measure for NP-complete problems. There is no reason to expect that if a problem appears in an arbitrarily chosen hierarchy, it should be complete for one of its levels.  
> **username_0**: I see, I had another error in reasoning: I somehow I thought every problem has to be complete for some level of SAT-oracle calls. But as you said, this must not be the case. Thank you a lot for your help that helped me understand things much better.  
> **username_0**: One more question: In your first paragraph, is $q(n)$ a polylogarithmic function (as it is in Gottlob/Fermüller) or a polynom?  
> **username_1**: It can be *any* function (though it only makes good sense if it is at most polynomial).  

---

