<p>This problem is NP-hard.</p>

<p>You can get 3-SAT with the gates <em>min</em>(<i>x</i>,<em>y</em>), <em>max</em>(<i>x,y</i>) and 1&minus;<em>x</em>.</p>

<p>What we want is to reduce a 3-SAT problem to a circuit for which you can get 1 if all the variables are satisfiable, and you can only achieve something strictly less than 1 otherwise.</p>

<p>We can force all the variables to be either 0 or 1 by taking a minimum of a lot of expressions, and make these expressions include <em>max</em>(<i>x</i>,1&minus;<i>x</i>).</p>

<p>Now for every clause in the 3-SAT problem <em>x</em>&vee;<em>y</em>&vee;<em>z</em>, we put the expression <em>max</em>(<i>x</i>,<em>y</em>,<i>z</i>) in the minimum.</p>

<p>I don't know what the optimal value is for a non-satisfiable 3-SAT problem, but it will be strictly less than 1. </p>

CC BY-SA 3.0
2013-02-13T19:41:38.613Z
Yes, NP-hardness is the "easy direction", as pointed in a comment above. In fact, if you do not use the average gate, but just min and max, it's easy to show that the maximal value is 1 if the corresponding Boolean circuit is satisfiable, and 1/2 otherwise (simply by plugging 1/2 to all the variables).
Anyway, the problem was solved in the comments above.
Shaull
CC BY-SA 3.0
2013-02-13T19:05:52.760Z
2013-02-13T19:05:52.760Z
Peter Shor 
<p>Not exactly what you asked for, but a context in which similar circuits appear.</p>

<p>If you remove the gate $1-x$ (which is not even mentioned in the title!) then what you get is a monotone arithmetic circuit. The classical monotone circuit lower bounds of Razborov have been extended to monotone arithmetic circuits (with the same results) by Pavel Pudlák, <a href="http://www.math.cas.cz/~pudlak/interpol.ps" rel="nofollow">Lower bounds for resolution and cutting planes proofs</a>.</p>

CC BY-SA 3.0
2013-02-13T14:56:12.187Z
Thanks.
In this case, however, if you remove the $1-x$ gate, then the problem is trivial - the maximal value is 1 and it's attained when all variables get value 1.
Shaull
CC BY-SA 3.0
2013-02-13T13:56:03.917Z
2013-02-13T13:56:03.917Z
Yuval Filmus
<p>The satisfiability problem for these circuits  (i.e., given a circuit $C$ and $u\in[0,1]$, decide whether there is an input $x$ such that $C(x)\ge u$) is in NP, and therefore NP-complete by Neal Young’s comment and Peter Shor’s answer.</p>

<p>We can construct a nondeterministic reduction of the problem to linear programming in the following way. Let $\{a_i:i&lt;m\}$ be all nodes of $C$ that are min or max gates (here $m\le n$, where $n$ is the size of the circuit), and let $b_i$ and $c_i$ be the input nodes of gate $a_i$. For every $i&lt;m$, choose one of the two additional constraints $b_i\le c_i$ or $c_i\le b_i$ (there are $2^m$ possible choices in total). When such a choice is fixed, we can simplify the circuit by replacing each $a_i$ with $b_i$ or $c_i$ as appropriate, and the resulting circuit can be described by a system of $n$ linear equations whose variables are the original input variables of the circuit, and additional variables corresponding to nodes of the circuit.</p>

<p>We also include $m$ inequalities stating that the extra constraints are satisfied, inequalities bounding the original input variables to $[0,1]$, and an inequality stating that the output node has value $\ge u$. Then this is a linear program of size $O(n)$ depending on the choice of the extra constraints, and the circuit attains value $\ge u$ iff there exists a choice of the constraints such that the associated linear program has a solution. Since linear programming is in P, this shows that the problem is in NP.</p>

<p>Also note that the optimum value of a linear program is attained at a vertex of the polytope. This means that the denominator of the optimal solution can be expressed as a determinant of a square matrix of dimension $O(n)$ whose entries are constant-size integers, and there are only $O(1)$ nonzero entries in each row, and as such it is bounded by $2^{O(n)}$.</p>

<p>Reductions of this kind are often useful to give upper bounds on the complexity of satisfiability in propositional fuzzy logics (such as Łukasiewicz logic) and related systems. (In fact, the original problem is a minor variant of satisfiability in Łukasiewicz, which would correspond to circuits with $\min(1,x+y)$ instead of $(x+y)/2$.) An overview of related results can be found in Chapter X of the Handbook of Mathematical Fuzzy Logic, Vol. II.</p>

CC BY-SA 3.0
2013-02-13T21:20:21.847Z
2013-02-13T21:20:21.847Z
Emil Jeřábek
<p>Consider a circuit that takes as inputs numbers in $[0,1]$, and has gates that consist of the functions $\max(x, y)$, $\min(x, y)$, $1 - x$, and $\frac{x+y}{2}$.
The output of the circuit is then also a number in $[0,1]$.</p>

<p>Does anyone know if this model, or a closely related model, has been studied? </p>

<p>Specifically, I'm trying to solve the satisfiability problem for this circuit, namely computing the maximum value that can be attained by this circuit (it indeed attains a maximum, as it represents a continuous function in a compact domain).</p>

<p>Remark: my study of this model is via weighted temporal logics, so any models that relate to the latter might also come in handy.</p>

CC BY-SA 3.0
2013-02-11T15:57:41.030Z
I am aware that having both min{x,y} and max{x,y} is redundant.
Shaull
CC BY-SA 3.0
2013-02-11T17:32:05.040Z
Surely this problem is NP-hard.  (Via satisfiability: you have $x\vee y \equiv \max\{x,y\}$ and $\neg x \equiv 1 - x$, with which you can do AND, OR, and NOT.)  So, is your question whether or not this problem is in NP?  The decision question of whether such a circuit has an input that yields value 1 seems to be in NP, since, if there is such an input, there is one that is 0/1.
Neal Young
CC BY-SA 3.0
2013-02-11T22:22:01.017Z
Indeed, @NealYoung. The problem from which I arrived at this (LTL Satisfiability) is PSPACE complete in the Boolean case, so NP doesn't bother me.
The question is not whether there is an input that yields 1, but rather what is the maximal value that can be attained. So it's not a decision problem.
I will remark that I do know how to solve the respective decision problem: given a threshold t, decide whether there exists an input that gives more than t. This is not very hard. 
So essentially, the question is - what do we do when we have no threshold?
Shaull
CC BY-SA 3.0
2013-02-11T22:51:01.770Z
If the circuit has $n$ gates, I think the maximum value is an integer multiple of $2^{-n}$.  If that's right, you can find the maximum value by binary search, using the decision algorithm as an oracle, with a factor $n$ penalty in the running time.  (I'm assuming the circuit is a directed _acyclic_ graph; the problem seems well-defined but much harder if the circuit has directed cycles and you're looking for some sort of fixed point.)
Jeffε
CC BY-SA 3.0
2013-02-11T23:14:01.933Z
@JɛﬀE: The maximum value is not necessarily a multiple of 2^(−n).  For example, the maximum of min(x, ((1−x)+y)/2) is 2/3, attained when x=2/3 and y=1.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-12T07:59:56.953Z
As @JɛﬀE points out, the connection between the maximum value and the "coefficients" in the circuit (i.e. 1/2) is not straightforward. It is also nice to observe that the maximum is attained at points which are not a power of 1/2.
My current direction of solving this is by proving that the function represented by the circuit is a patching of linear functions in each variable, and somehow using this to bound the length of the description of the solution.
Shaull
CC BY-SA 3.0
2013-02-12T08:12:50.303Z
What is your model of computation? Because in the boolean settings, I do not see how to handle an arbitrary threshold $t$. I may be missing something though!
Bruno
CC BY-SA 3.0
2013-02-12T08:17:41.767Z
Sorry, you are right. What I thought was a solution for the threshold case was based on a different model.
So the threshold problem is also open.
Shaull
CC BY-SA 3.0
2013-02-12T17:02:48.683Z
@TsuyoshiIto: Oops. Thanks for the counterexample!  It still seems likely that the maximum value is a rational number with denominator less than $2^{O(n^2)}$, which means binary search should still work with polynomial overhead (using [the Stern-Brocot](http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree) instead of bits to guide the search).
Jeffε
CC BY-SA 3.0
2013-02-12T17:06:43.610Z
@JɛﬀE: Exactly what I'm trying to prove (the $O(n^2)$ is less critical for me, I'll settle for any bound). I agree that it seems likely, since the circuit represents a seemingly simple function. Still, so far I am unable to prove it.
Shaull
CC BY-SA 3.0
2013-02-12T17:24:42.547Z
@JɛﬀE: I agree that the denominator of the optimal value is probably at most 2^poly(n).  2^(O(n^2)) also sounds plausible but I am not sure.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-13T14:32:45.637Z
If we nondeterministically choose one of the $\le2^n$ possible truth values for $x\le y$, where $x,y$ are all pairs of nodes such that a $\min(x,y)$ or $\max(x,y)$ node appears in the circuit, this turns into a linear programming problem, which is solvable in P. Thus, the decision version of the original maximization problem is in NP. (This is a variant of the satisfiability problem in Łukasiewicz logic, so you might want to look at Haniková’s chapter in the Handbook of Mathematical Fuzzy Logic for related information.)
Emil Jeřábek
CC BY-SA 3.0
2013-02-13T15:47:07.027Z
Neal Young’s comment and Emil Jeřábek’s comment together show that the decision version of this optimization problem is NP-complete.  Did those comments answer your question, or is there anything left unanswered?
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-13T16:16:28.793Z
I don't fully understand what @EmilJeřábek means by "possible truth values", as there are infinitely many of these, but the gist of it makes sense indeed. I will read the references, and if there is anything left open, I will ask again. 
Thanks!
Shaull
CC BY-SA 3.0
2013-02-13T17:06:48.967Z
@Shaull: Let me describe it in more detail. Let $\{a_i:i<m\}$ be the nodes of the circuit that are min or max gates (here $m$ is bounded by the size of the circuit), and let $b_i$ and $c_i$ be the input nodes of gate $a_i$. For every $i<m$, choose an additional constraint $b_i\le c_i$ or $c_i\le b_i$. There are $2^m$ such choices. When such a choice is fixed, you can simplify the circuit by replacing $a_i$ with $b_i$ or $c_i$ as appropriate, hence it turns into a system of linear equations whose variables are the original variables of the problem, and additional variables corresponding to ...
Emil Jeřábek
CC BY-SA 3.0
2013-02-13T17:10:21.380Z
... nodes in the circuit. Include $m$ inequalities stating that the extra constraints are satisfied, inequalities bounding the original variables to $[0,1]$, and an inequality stating that the output node has value $\ge u$. Then this is a linear program depending on the choice of the extra constraints, and the circuit attains value $\ge u$ iff there exists a choice of the constraints such that the associated linear program has a solution.
Emil Jeřábek
CC BY-SA 3.0
2013-02-13T17:17:50.853Z
@EmilJeřábek : This is a very nice technique which I was not aware of. Thanks!
This fully answers my question.
Shaull
CC BY-SA 3.0
2013-02-13T17:18:39.200Z
Also note that the optimum value of a linear program is attained at a vertex of the polytope. This means that the denominator of the optimal solution can be expressed as a determinant of a matrix of dimension $O(n)$ whose entries are constant-size integers, and there are only $O(1)$ nonzero entries in each row, and as such it is bounded by $2^{O(n)}$.
Emil Jeřábek
CC BY-SA 3.0
2013-02-13T17:22:22.687Z
@EmilJeřábek: Great comments!  You should make that a proper answer :-)
Michaël Cadilhac
<arithmetic-circuits>
Arithmetic circuits with $\min$, $\max$, and average over $[0,1]$
Shaull
# Arithmetic circuits with $\min$, $\max$, and average over $[0,1]$

(Asked by: username_0 on 2013-02-11)

Consider a circuit that takes as inputs numbers in $[0,1]$, and has gates that consist of the functions $\max(x, y)$, $\min(x, y)$, $1 - x$, and $\frac{x+y}{2}$.
The output of the circuit is then also a number in $[0,1]$.

Does anyone know if this model, or a closely related model, has been studied?

Specifically, I'm trying to solve the satisfiability problem for this circuit, namely computing the maximum value that can be attained by this circuit (it indeed attains a maximum, as it represents a continuous function in a compact domain).

Remark: my study of this model is via weighted temporal logics, so any models that relate to the latter might also come in handy.

**Tags:** arithmetic-circuits

> **Comments:**
> **username_0**: I am aware that having both min{x,y} and max{x,y} is redundant.  
> **username_1**: Surely this problem is NP-hard.  (Via satisfiability: you have $x\vee y \equiv \max\{x,y\}$ and $\neg x \equiv 1 - x$, with which you can do AND, OR, and NOT.)  So, is your question whether or not this problem is in NP?  The decision question of whether such a circuit has an input that yields value 1 seems to be in NP, since, if there is such an input, there is one that is 0/1.  
> **username_0**: Indeed, @NealYoung. The problem from which I arrived at this (LTL Satisfiability) is PSPACE complete in the Boolean case, so NP doesn't bother me. The question is not whether there is an input that yields 1, but rather what is the maximal value that can be attained. So it's not a decision problem. I will remark that I do know how to solve the respective decision problem: given a threshold t, decide whether there exists an input that gives more than t. This is not very hard.  So essentially, the question is - what do we do when we have no threshold?  
> **username_2**: If the circuit has $n$ gates, I think the maximum value is an integer multiple of $2^{-n}$.  If that's right, you can find the maximum value by binary search, using the decision algorithm as an oracle, with a factor $n$ penalty in the running time.  (I'm assuming the circuit is a directed _acyclic_ graph; the problem seems well-defined but much harder if the circuit has directed cycles and you're looking for some sort of fixed point.)  
> **username_3**: @JɛﬀE: The maximum value is not necessarily a multiple of 2^(−n).  For example, the maximum of min(x, ((1−x)+y)/2) is 2/3, attained when x=2/3 and y=1.  
> **username_0**: As @JɛﬀE points out, the connection between the maximum value and the "coefficients" in the circuit (i.e. 1/2) is not straightforward. It is also nice to observe that the maximum is attained at points which are not a power of 1/2. My current direction of solving this is by proving that the function represented by the circuit is a patching of linear functions in each variable, and somehow using this to bound the length of the description of the solution.  
> **username_4**: What is your model of computation? Because in the boolean settings, I do not see how to handle an arbitrary threshold $t$. I may be missing something though!  
> **username_0**: Sorry, you are right. What I thought was a solution for the threshold case was based on a different model. So the threshold problem is also open.  
> **username_2**: @TsuyoshiIto: Oops. Thanks for the counterexample!  It still seems likely that the maximum value is a rational number with denominator less than $2^{O(n^2)}$, which means binary search should still work with polynomial overhead (using [the Stern-Brocot](http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree) instead of bits to guide the search).  
> **username_0**: @JɛﬀE: Exactly what I'm trying to prove (the $O(n^2)$ is less critical for me, I'll settle for any bound). I agree that it seems likely, since the circuit represents a seemingly simple function. Still, so far I am unable to prove it.  
> **username_3**: @JɛﬀE: I agree that the denominator of the optimal value is probably at most 2^poly(n).  2^(O(n^2)) also sounds plausible but I am not sure.  
> **username_5**: If we nondeterministically choose one of the $\le2^n$ possible truth values for $x\le y$, where $x,y$ are all pairs of nodes such that a $\min(x,y)$ or $\max(x,y)$ node appears in the circuit, this turns into a linear programming problem, which is solvable in P. Thus, the decision version of the original maximization problem is in NP. (This is a variant of the satisfiability problem in Łukasiewicz logic, so you might want to look at Haniková’s chapter in the Handbook of Mathematical Fuzzy Logic for related information.)  
> **username_3**: username_1’s comment and username_5’s comment together show that the decision version of this optimization problem is NP-complete.  Did those comments answer your question, or is there anything left unanswered?  
> **username_0**: I don't fully understand what @EmilJeřábek means by "possible truth values", as there are infinitely many of these, but the gist of it makes sense indeed. I will read the references, and if there is anything left open, I will ask again.  Thanks!  
> **username_5**: @username_0: Let me describe it in more detail. Let $\{a_i:i<m\}$ be the nodes of the circuit that are min or max gates (here $m$ is bounded by the size of the circuit), and let $b_i$ and $c_i$ be the input nodes of gate $a_i$. For every $i<m$, choose an additional constraint $b_i\le c_i$ or $c_i\le b_i$. There are $2^m$ such choices. When such a choice is fixed, you can simplify the circuit by replacing $a_i$ with $b_i$ or $c_i$ as appropriate, hence it turns into a system of linear equations whose variables are the original variables of the problem, and additional variables corresponding to ...  
> **username_5**: ... nodes in the circuit. Include $m$ inequalities stating that the extra constraints are satisfied, inequalities bounding the original variables to $[0,1]$, and an inequality stating that the output node has value $\ge u$. Then this is a linear program depending on the choice of the extra constraints, and the circuit attains value $\ge u$ iff there exists a choice of the constraints such that the associated linear program has a solution.  
> **username_0**: @EmilJeřábek : This is a very nice technique which I was not aware of. Thanks! This fully answers my question.  
> **username_5**: Also note that the optimum value of a linear program is attained at a vertex of the polytope. This means that the denominator of the optimal solution can be expressed as a determinant of a matrix of dimension $O(n)$ whose entries are constant-size integers, and there are only $O(1)$ nonzero entries in each row, and as such it is bounded by $2^{O(n)}$.  
> **username_6**: @EmilJeřábek: Great comments!  You should make that a proper answer :-)  

---

## 3 answers

### Answer by username_5 on 2013-02-13. Score: 12 | Accepted answer

The satisfiability problem for these circuits (i.e., given a circuit $C$ and $u\in[0,1]$, decide whether there is an input $x$ such that $C(x)\ge u$) is in NP, and therefore NP-complete by username_1’s comment and Peter Shor’s answer.

We can construct a nondeterministic reduction of the problem to linear programming in the following way. Let $\{a\_i:i

We also include $m$ inequalities stating that the extra constraints are satisfied, inequalities bounding the original input variables to $[0,1]$, and an inequality stating that the output node has value $\ge u$. Then this is a linear program of size $O(n)$ depending on the choice of the extra constraints, and the circuit attains value $\ge u$ iff there exists a choice of the constraints such that the associated linear program has a solution. Since linear programming is in P, this shows that the problem is in NP.

Also note that the optimum value of a linear program is attained at a vertex of the polytope. This means that the denominator of the optimal solution can be expressed as a determinant of a square matrix of dimension $O(n)$ whose entries are constant-size integers, and there are only $O(1)$ nonzero entries in each row, and as such it is bounded by $2^{O(n)}$.

Reductions of this kind are often useful to give upper bounds on the complexity of satisfiability in propositional fuzzy logics (such as Łukasiewicz logic) and related systems. (In fact, the original problem is a minor variant of satisfiability in Łukasiewicz, which would correspond to circuits with $\min(1,x+y)$ instead of $(x+y)/2$.) An overview of related results can be found in Chapter X of the Handbook of Mathematical Fuzzy Logic, Vol. II.


---

### Answer by username_7 on 2013-02-13. Score: 4

This problem is NP-hard.

You can get 3-SAT with the gates *min*(*x*,*y*), *max*(*x,y*) and 1−*x*.

What we want is to reduce a 3-SAT problem to a circuit for which you can get 1 if all the variables are satisfiable, and you can only achieve something strictly less than 1 otherwise.

We can force all the variables to be either 0 or 1 by taking a minimum of a lot of expressions, and make these expressions include *max*(*x*,1−*x*).

Now for every clause in the 3-SAT problem *x*∨*y*∨*z*, we put the expression *max*(*x*,*y*,*z*) in the minimum.

I don't know what the optimal value is for a non-satisfiable 3-SAT problem, but it will be strictly less than 1.

> **Comments:**
> **username_0**: Yes, NP-hardness is the "easy direction", as pointed in a comment above. In fact, if you do not use the average gate, but just min and max, it's easy to show that the maximal value is 1 if the corresponding Boolean circuit is satisfiable, and 1/2 otherwise (simply by plugging 1/2 to all the variables). Anyway, the problem was solved in the comments above.  

---

### Answer by username_8 on 2013-02-13. Score: 1

Not exactly what you asked for, but a context in which similar circuits appear.

If you remove the gate $1-x$ (which is not even mentioned in the title!) then what you get is a monotone arithmetic circuit. The classical monotone circuit lower bounds of Razborov have been extended to monotone arithmetic circuits (with the same results) by Pavel Pudlák, [Lower bounds for resolution and cutting planes proofs](http://www.math.cas.cz/~pudlak/interpol.ps).

> **Comments:**
> **username_0**: Thanks. In this case, however, if you remove the $1-x$ gate, then the problem is trivial - the maximal value is 1 and it's attained when all variables get value 1.  

---

