<p>(1) has a polynomial solution. Consider a graph with source $s$, sink $t$, vertices $U$ corresponding to the variables and vertices $V$ corresponding to the functions. If $f_j = x_1 \land \ldots \land x_k$ then add edges $f_j \to x_i$ for each $i \in \{1,\ldots,k\}$ with capacities equal to $C$ for $C &gt; \sum p_j$. Add edges $x_i \to t$ with capacities $c_i$ and edges $s \to f_j$ with capacities $p_j$. Consider minimum cut between $s$ and $t$ in this graph (it could be easily found with almost any maximal-flow algrorithm). Let $U_s \subseteq U$ and $V_s \subseteq V$ be the sets of vertices in the component of $s$. Then the value of the minimum cut is $$\sum\limits_{i \in U_s} c_i + \sum\limits_{j \not\in V_s} f_j = \underbrace{\sum\limits_{j\in V} f_j}_{\text{constant}} - \underbrace{\left(-\sum\limits_{i \in U_s} c_i + \sum\limits_{j \in V_s} f_j\right)}_{\text{objective function}}$$
Thus if this value is minimised, the objective function is maximised. On the other hand $U_s$ and $V_s$ for minimum cut have the property that if $x_1 \land \ldots \land  x_k = f_j \in V_s$ then $x_1, \ldots, x_k \in U_s$ since otherwise the value of the cut is $\ge C$ which is not optimal. Thus setting $x=1$ for $x \in U_s$ and $x=0$ for $x \not\in U_s$ gives an optimal solution for (1).</p>

<p>The case with arbitrary $p_j$ is $\mathbf{NP}\text{-}\mathrm{complete}$ even with polynomially-bounded $|p_j|$.</p>

<p><strong>If you allow $p_j$ to be negative</strong>, you can reduce $\mathrm{max}\text{-}\mathrm{SAT}$ to this problem. For each variable $x_i$ of $\mathrm{max}\text{-}\mathrm{SAT}$ add two variables $x_i$ and $\lnot x_i$ to your input. For each of these pair add the condition $x_i \land \lnot x_i$ with the cost $-C$ for a large enough constant $C$. For all clauses of $\mathrm{max}\text{-}\mathrm{SAT}$ input add the corresponding conjunction with all literals reversed: $x \lor \lnot y \lor z$ becomes $\lnot x \land y \land \lnot z$ (here $\lnot x$ and $\lnot z$ are variables in the new problem). $\lnot x \land y \land \lnot z \iff \lnot (x \lor \lnot y \lor z)$ therefore each unsatisfied conjunctions correspond to satisfied clauses. Thus you can set the cost $p$ for each conjunction as $-1$. For $c_i = 0$ for all $i \in \{1,\ldots, n\}$, $m -\max \left\{\sum\limits_j f_j p_j - \sum\limits_i a_i c_i\right\}$ (where $m$ is the number of clauses in the $\mathrm{max}\text{-}\mathrm{SAT}$ instance) is the maximum number of clauses that could be satisfied in the instance of $\mathrm{max}\text{-}\mathrm{SAT}$ or a value greater than or equal to $C - n$ if the instance is unsatisfiable. Thus $C = 3n$ is "big enough". I.e. for negative $p_j$ there is no polynomial solution even with bounded $|p_j|$ and $|c_j|$ unless $\mathbf{P} = \mathbf{NP}$.</p>

CC BY-SA 3.0
2018-01-07T19:41:39.013Z
thanks! it's really interesting how a (seemingly) small change leads to such a drastic difference in complexity.
AmeerJ
CC BY-SA 3.0
2018-01-07T12:42:55.533Z
2018-01-07T18:40:29.090Z
2018-01-07T18:40:29.090Z
Artur Riazanov
<p>Suppose we have a set of binary variables $a_1, ..., a_n$ that $a_i\in\{0,1\}$. Now we define $m$ and functions over a subset of them: $$j\in\{1,...,m\}: f_j=x_1\land x_2\land...\land  x_k$$ in which 
$$\{x_1,...,x_k\}\subset\{a_1,...,a_n\}$$</p>

<p>Suppose that each variable $a_i$ has also a cost $c_i$ assigned to it and every function $f_j$ has a profit $p_j$ associated with it. Both variables are non-negative $\forall i,j: p_j,c_i\ge 0$.</p>

<p>The problem is how to maximise profits minus costs over the set of all possible $a_i$s:
$$(1) \max_{a_1,...,a_n} \left\{\sum_j^m p_j f_j - \sum_i^n c_i a_i \right\}$$</p>

<p>Another related problem is to maximise the profit with constrained costs for some constant $C$: 
$$(2)   \max_{\sum_i c_i a_i \le C} \left\{\sum_j^n p_j f_j \right\}$$.</p>

<p>Now here here the questions I have: </p>

<ol>
<li>Can $(1)$ be solved in a strictly polynomial, or
pseudo-polynomial way?  </li>
<li>Can $(2)$ be solved in
pseudo-polynomial time?</li>
</ol>

<p>By pseudo-polynomial we mean assuming bounds on $|c_i|$ and $|p_j|$, can a polynomial time algorithm be achieved? </p>

<p>It's clear that if $(2)$ pseudo-polynomial solution $(1)$ will also have a pseudo-polynomial solution, by iterating over various values of $C$. Therefore in some sense $(2)$ is a more difficult problem. Moreover, knapsack can be seen as a special case of $(2)$ if we set $f_j=a_j$. Therefore it can't be strictly polynomial. But I can't tell much more about the complexity of these two problems. </p>

CC BY-SA 3.0
2018-01-07T12:34:03.190Z
The version of the knapsack problem you described  (with $f_j = a_j$) can be easily solved, you simply set $a_i = 1$ if $c_i \ge p_i$ and set $a_i = 0$ otherwise.
Artur Riazanov
CC BY-SA 3.0
2018-01-07T15:13:32.093Z
@ArturRyazanov you are right, so maximising the difference is an easier problem than the original knapsack, which is only pseudo polynomial.
AmeerJ
CC BY-SA 3.0
2018-01-07T18:04:15.293Z
$k-\mathrm{CLIQUE}$ can be reduced to (2). Create a variable for each vertex, set all $c_i = 1$, $C=k$ and for each edge $(u,v)$ add the function $u \land v$ with $p=1$. The answer for this instance of (2)  equals $\binom{k}{2}$ iff the given graph has $k$-CLIQUE. Thus (2) has no pseudo-polynomial algorithm.
Artur Riazanov
CC BY-SA 3.0
2018-01-07T18:45:52.247Z
One could do the same for (1): for a case that $f_j$s have only two operands construct a similar graph, $c_i$ cost for vertex $i$ and $p_{ij}$ profit for edge $e(i,j)$ if it exists. Then the problem becomes: choose a subset of vertices with the biggest profit-cost margin. Is this a studied problem, or related to a studied problem?
AmeerJ
CC BY-SA 3.0
2018-01-07T18:48:27.013Z
I think (1) is, in fact, polynomially-solvable (not completely sure though), I've updated my answer.
Artur Riazanov
<cc.complexity-theory><circuit-complexity>
Complexity of maximising weighted sum of and functions on a set of binary variables
AmeerJ
# Complexity of maximising weighted sum of and functions on a set of binary variables

(Asked by: username_0 on 2018-01-07)

Suppose we have a set of binary variables $a\_1, ..., a\_n$ that $a\_i\in\{0,1\}$. Now we define $m$ and functions over a subset of them: $$j\in\{1,...,m\}: f\_j=x\_1\land x\_2\land...\land x\_k$$ in which
$$\{x\_1,...,x\_k\}\subset\{a\_1,...,a\_n\}$$

Suppose that each variable $a\_i$ has also a cost $c\_i$ assigned to it and every function $f\_j$ has a profit $p\_j$ associated with it. Both variables are non-negative $\forall i,j: p\_j,c\_i\ge 0$.

The problem is how to maximise profits minus costs over the set of all possible $a\_i$s:
$$(1) \max\_{a\_1,...,a\_n} \left\{\sum\_j^m p\_j f\_j - \sum\_i^n c\_i a\_i \right\}$$

Another related problem is to maximise the profit with constrained costs for some constant $C$:
$$(2) \max\_{\sum\_i c\_i a\_i \le C} \left\{\sum\_j^n p\_j f\_j \right\}$$.

Now here here the questions I have:

1. Can $(1)$ be solved in a strictly polynomial, or
   pseudo-polynomial way?
2. Can $(2)$ be solved in
   pseudo-polynomial time?

By pseudo-polynomial we mean assuming bounds on $|c\_i|$ and $|p\_j|$, can a polynomial time algorithm be achieved?

It's clear that if $(2)$ pseudo-polynomial solution $(1)$ will also have a pseudo-polynomial solution, by iterating over various values of $C$. Therefore in some sense $(2)$ is a more difficult problem. Moreover, knapsack can be seen as a special case of $(2)$ if we set $f\_j=a\_j$. Therefore it can't be strictly polynomial. But I can't tell much more about the complexity of these two problems.

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: The version of the knapsack problem you described  (with $f_j = a_j$) can be easily solved, you simply set $a_i = 1$ if $c_i \ge p_i$ and set $a_i = 0$ otherwise.  
> **username_0**: @ArturRyazanov you are right, so maximising the difference is an easier problem than the original knapsack, which is only pseudo polynomial.  
> **username_1**: $k-\mathrm{CLIQUE}$ can be reduced to (2). Create a variable for each vertex, set all $c_i = 1$, $C=k$ and for each edge $(u,v)$ add the function $u \land v$ with $p=1$. The answer for this instance of (2)  equals $\binom{k}{2}$ iff the given graph has $k$-CLIQUE. Thus (2) has no pseudo-polynomial algorithm.  
> **username_0**: One could do the same for (1): for a case that $f_j$s have only two operands construct a similar graph, $c_i$ cost for vertex $i$ and $p_{ij}$ profit for edge $e(i,j)$ if it exists. Then the problem becomes: choose a subset of vertices with the biggest profit-cost margin. Is this a studied problem, or related to a studied problem?  
> **username_1**: I think (1) is, in fact, polynomially-solvable (not completely sure though), I've updated my answer.  

---

## 1 answers

### Answer by username_1 on 2018-01-07. Score: 2 | Accepted answer

(1) has a polynomial solution. Consider a graph with source $s$, sink $t$, vertices $U$ corresponding to the variables and vertices $V$ corresponding to the functions. If $f\_j = x\_1 \land \ldots \land x\_k$ then add edges $f\_j \to x\_i$ for each $i \in \{1,\ldots,k\}$ with capacities equal to $C$ for $C > \sum p\_j$. Add edges $x\_i \to t$ with capacities $c\_i$ and edges $s \to f\_j$ with capacities $p\_j$. Consider minimum cut between $s$ and $t$ in this graph (it could be easily found with almost any maximal-flow algrorithm). Let $U\_s \subseteq U$ and $V\_s \subseteq V$ be the sets of vertices in the component of $s$. Then the value of the minimum cut is $$\sum\limits\_{i \in U\_s} c\_i + \sum\limits\_{j \not\in V\_s} f\_j = \underbrace{\sum\limits\_{j\in V} f\_j}\_{\text{constant}} - \underbrace{\left(-\sum\limits\_{i \in U\_s} c\_i + \sum\limits\_{j \in V\_s} f\_j\right)}\_{\text{objective function}}$$
Thus if this value is minimised, the objective function is maximised. On the other hand $U\_s$ and $V\_s$ for minimum cut have the property that if $x\_1 \land \ldots \land x\_k = f\_j \in V\_s$ then $x\_1, \ldots, x\_k \in U\_s$ since otherwise the value of the cut is $\ge C$ which is not optimal. Thus setting $x=1$ for $x \in U\_s$ and $x=0$ for $x \not\in U\_s$ gives an optimal solution for (1).

The case with arbitrary $p\_j$ is $\mathbf{NP}\text{-}\mathrm{complete}$ even with polynomially-bounded $|p\_j|$.

**If you allow $p\_j$ to be negative**, you can reduce $\mathrm{max}\text{-}\mathrm{SAT}$ to this problem. For each variable $x\_i$ of $\mathrm{max}\text{-}\mathrm{SAT}$ add two variables $x\_i$ and $\lnot x\_i$ to your input. For each of these pair add the condition $x\_i \land \lnot x\_i$ with the cost $-C$ for a large enough constant $C$. For all clauses of $\mathrm{max}\text{-}\mathrm{SAT}$ input add the corresponding conjunction with all literals reversed: $x \lor \lnot y \lor z$ becomes $\lnot x \land y \land \lnot z$ (here $\lnot x$ and $\lnot z$ are variables in the new problem). $\lnot x \land y \land \lnot z \iff \lnot (x \lor \lnot y \lor z)$ therefore each unsatisfied conjunctions correspond to satisfied clauses. Thus you can set the cost $p$ for each conjunction as $-1$. For $c\_i = 0$ for all $i \in \{1,\ldots, n\}$, $m -\max \left\{\sum\limits\_j f\_j p\_j - \sum\limits\_i a\_i c\_i\right\}$ (where $m$ is the number of clauses in the $\mathrm{max}\text{-}\mathrm{SAT}$ instance) is the maximum number of clauses that could be satisfied in the instance of $\mathrm{max}\text{-}\mathrm{SAT}$ or a value greater than or equal to $C - n$ if the instance is unsatisfiable. Thus $C = 3n$ is "big enough". I.e. for negative $p\_j$ there is no polynomial solution even with bounded $|p\_j|$ and $|c\_j|$ unless $\mathbf{P} = \mathbf{NP}$.

> **Comments:**
> **username_0**: thanks! it's really interesting how a (seemingly) small change leads to such a drastic difference in complexity.  

---

