Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 11 down vote favorite
2

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.

share|improve this question
5  
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 Feb 11 at 17:32
3  
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 Feb 13 at 14:32
5  
@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 Feb 13 at 17:06
4  
... 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 Feb 13 at 17:10
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)}$. – Emil Jeřábek Feb 13 at 17:18
show 14 more comments

3 Answers

up vote 13 down vote accepted

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.

We can construct a nondeterministic reduction of the problem to linear programming in the following way. Let $\{a_i:i<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<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.

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.

share|improve this answer
up vote 4 down vote

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.

share|improve this answer
2  
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 Feb 13 at 19:41
up vote 1 down vote

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.

share|improve this answer
3  
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 Feb 13 at 14:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.