<p>Suppose I have a #P-hard function $f(S,x)$ where $x\in T$. Is the problem of $\arg\max_x f(S,x)$ guaranteed to be intractable?</p>

<p>If so, I want to see some references on this topic. If not, is there a general approach to prove such intractability for some typical problems?</p>

<p>For example, we know that S-Set Connectedness is #P-complete <a href="http://epubs.siam.org/doi/pdf/10.1137/0208032" rel="nofollow">1</a>. Is finding the node with maximum connectedness with a particular set also intractable?</p>

<p>Thank you very much!</p>

CC BY-SA 3.0
2014-07-10T07:12:29.637Z
Just a clarification, what are $S$, $T$ ? In the case, for example, of the #P-complete function that counts the number of satisfying assignments of a 3SAT formula ( $\# SAT(x)$ ).
Marzio De Biasi
CC BY-SA 3.0
2014-07-10T19:42:05.623Z
@MarzioDeBiasi I think in this case, $S$ is useless, $T$ is a set of 3-CNF formulae, and the problem is finding the formula in $T$ that has maximum number of satisfying assignments.
james
CC BY-SA 3.0
2014-07-10T22:12:07.090Z
ok! You can prove that the problem is intractable ($\#P$-complete) using the following approach: given a SAT formula $\varphi$ you can calculate $\#SAT(\varphi)$, using a sequence of $T_i = \{\varphi, F_n \}$ where $F_n$ is a custom-built formula having exactly $n$ satisfying assignments. If $argmax$ returns $F_n$ then you pick $T_{i+1} = \{ \varphi, F_{n/2} \}$ where $F_{n/2}$ has exactly $n/2$ satisfying assignments, otherwise you pick $T_{i+1} = \{ \varphi, F_{2n}\}$; and so on. Informally, you make a sort of binary search using $argmax$.
Marzio De Biasi
<complexity-classes>
Maximizing a #P-hard function
james
# Maximizing a #P-hard function

(Asked by: username_0 on 2014-07-10)

Suppose I have a #P-hard function $f(S,x)$ where $x\in T$. Is the problem of $\arg\max\_x f(S,x)$ guaranteed to be intractable?

If so, I want to see some references on this topic. If not, is there a general approach to prove such intractability for some typical problems?

For example, we know that S-Set Connectedness is #P-complete [1](http://epubs.siam.org/doi/pdf/10.1137/0208032). Is finding the node with maximum connectedness with a particular set also intractable?

Thank you very much!

**Tags:** complexity-classes
> **Comments:**
> **username_1**: Just a clarification, what are $S$, $T$ ? In the case, for example, of the #P-complete function that counts the number of satisfying assignments of a 3SAT formula ( $\# SAT(x)$ ).  
> **username_0**: @MarzioDeBiasi I think in this case, $S$ is useless, $T$ is a set of 3-CNF formulae, and the problem is finding the formula in $T$ that has maximum number of satisfying assignments.  
> **username_1**: ok! You can prove that the problem is intractable ($\#P$-complete) using the following approach: given a SAT formula $\varphi$ you can calculate $\#SAT(\varphi)$, using a sequence of $T_i = \{\varphi, F_n \}$ where $F_n$ is a custom-built formula having exactly $n$ satisfying assignments. If $argmax$ returns $F_n$ then you pick $T_{i+1} = \{ \varphi, F_{n/2} \}$ where $F_{n/2}$ has exactly $n/2$ satisfying assignments, otherwise you pick $T_{i+1} = \{ \varphi, F_{2n}\}$; and so on. Informally, you make a sort of binary search using $argmax$.  

---

## 0 answers

