<p>With addition and subtraction, I think the <a href="http://en.wikipedia.org/wiki/Partition_problem">Partition problem</a>, which is NP-hard, reduces to your second problem.</p>

<p>Given a set $S = \{s_1, s_2, \ldots, s_n\}$ we create the problem </p>

<p>$s_1$ $op_1$ $s_2$ $op_2$ $s_3$ $op_3$ $\ldots op_{n-1}$ $s_n = 0$.  </p>

<p>If a solution exists, we create two sets:</p>

<p>$S_1 = \{s_1\}\cup \{s_i | op_{i-1} = +\}$</p>

<p>$S_2 =  \{s_i | op_{i-1} = -\}$</p>

<p>These two sets have to have the same sum by the setup of our original problem, so the partition problem is solved.  This shows that not only is coming up with the actual solution to this problem hard, it's in fact NP hard to determine if a solution exists (at least for addition and subtraction).</p>

<p>For a set of operations that doesn't allow creation of negative integers, say multiplication and addition, it's not so clear.  Also, this only shows that the problem is weakly NP-hard; there may be a reduction that gives a stronger result than this.</p>

CC BY-SA 3.0
2012-08-13T05:25:28.260Z
I think your proof can be adapted to the $\times/\div$ case fairly easily, just set the target problem to $s_{1}\ldots s_{n} = 1$. Then a solution implies the denominator is the same as the numerator (assuming $s_{i} > 0$ for all $i$). Of course this doesn't give the four operator case, but then we'd also have to handle order of operations.
Luke Mathieson
CC BY-SA 3.0
2012-08-14T03:01:12.687Z
Thanks, @Sam and Luke. What if we mix all four operators? Intuitively having more operators will only make the problem more complex, but I don't see a straight-forward proof.
DSounders
CC BY-SA 3.0
2012-08-14T03:49:29.430Z
Still thinking about all four. We can also get $+/\div$ easily, but that's still only two at a time.
Luke Mathieson
CC BY-SA 3.0
2012-08-14T03:54:37.287Z
Also, a reference for the (strong) $NP$-completeness of PRODUCT PARTITION: "“Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation" http://www.sciencedirect.com/science/article/pii/S0377221710003905
Luke Mathieson
CC BY-SA 3.0
2012-08-12T05:36:23.430Z
2012-08-12T13:54:27.173Z
2012-08-12T13:54:27.173Z
SamM
<p><strong>Short answer.</strong> The operator version of <strong>SAT</strong> is efficiently solvable &mdash; at least, if we assume arbitrary circuits of two-input gates with no fan-out, over any desired choice of gate-set.</p>

<p><strong>Long answer.</strong>
I assume the following form of the boolean problem:</p>

<blockquote>
  <p><strong>2-TREE-OPSAT.</strong> Given an input $x \in \{0,1\}^n$ for $n \geqslant 2$ and a gate set $\mathcal G$ consisting of 2-input one-output gates, does there exists a circuit $C$ consisting of  gates in $\mathcal G$ which <em>accepts</em> $x$, that is, which is satisfied when given the input $x$ (mapping bits of $x$ to the leaves of the circuit $C$ in-order)?</p>
</blockquote>

<p>In particular, we impose no particular structure on the circuits $C$ (aside from being binary trees), do not allow fan-out (so that each bit of $x$ is used only once), and the gates may be asymmetric. By allowing only two-bit gates, I exclude the <strong>NOT</strong> gate (but which may be simulated by having multiple gates which are related to each other by negations, such as <strong>AND</strong>/<strong>NAND</strong>; and I also exclude gates that simply output constants with no inputs, so that the number of gates in the circuit will in fact always be $n-1$ for an $n$-bit input. For the sake of brevity, I will refer to <strong>2-TREE-OPSAT</strong> below simply as <strong>OPSAT</strong>; though analysis of the problem may become much more difficult for circuits allowing arbitrary <em>k</em>-input gates (<strong>k-TREE-OPSAT</strong>) or allowing fan-out (which we might call <strong>k-FANOUT-OPSAT</strong>).</p>

<p>[<em>Edited to add</em>: we can easily adapt this to consider the more general problem of the current revision of your question, in which we attempt to map a given $x \in \{0,1\}^\ast$ to a target value $b \in \{0,1\}$, by interchanging the roles of $0$ and $1$ in the analysis below; this has the effect of interchanging the roles of <strong>AND</strong> and <strong>OR</strong>, <strong>NAND</strong> and <strong>NOR</strong>, <em>etc.</em>] 
$\def\et{\wedge}\def\ou{\vee}\def\AND{\mathop{\text{AND}}}\def\NAND{\mathop{\text{NAND}}}\def\OR{\mathop{\text{OR}}}\def\NOR{\mathop{\text{NOR}}}\def\EQUAL{\mathop{\text{EQUAL}}}\def\PARITY{\mathop{\text{PARITY}}}$</p>

<p>For a fixed choice of $x \in \{0,1\}^n$, the problem of choosing a suitable tree with suitable gates is not unlike a logical disjunction: using equivalences such as 
$$ \OR(x,y) \;\equiv\;\Bigl(\AND(x,y) \;\ou\; \PARITY(x,y)\Bigr) $$
we may perform reductions between collections relating more complicated gate sets to simple (and powerful) gate sets; a may speak of one gate set being able to emulate other gates not belonging to the set, by wisely choosing some element of $\mathcal G$ which has the same effect (when presented with a particular input) as a gate $G \notin \mathcal G$. In particular, certain combinations of gates (such as $\{ \OR, \NAND \}$) can simulate the constant function yielding $1$: we say that such gate-sets are <em>tautologous</em>.</p>

<p>We proceed by considering gate sets including different types of gates $G$, later excluding those gates from later cases of the analysis, to show that gate-sets involving any single one of the gates leads to a tractible problem. We will proceed in the order of the number of two-bit strings which satisfy the gate in question, starting from the constant $1$ gate to the constant $0$ gate.</p>

<ol>
<li><p>For any gate set $\mathcal G$ which contains the constant gate $G(x,y) = 1$, we may simply build a circuit $C$ using that gate alone, in which case $C$ accepts any $x$.</p></li>
<li><p><strong>OR and NAND.</strong> For any gate set $\mathcal G$ which contains $\OR$: if all other gates $G \in \mathcal G$ satisfy $G(x,y) \implies \OR(x,y)$, then there is no advantage to choosing any other gate but $\OR$ in building the circuit $C$. A circuit of only $\OR$ gates accepts any string except $x \in 0^\ast$.  Otherwise, there exists a gate $G \in \mathcal G$ such that $\{G, \OR\}$ is tautologous. So any instance of <strong>OPSAT</strong> with $\OR \in \mathcal G$ is easy; and similar remarks apply for $\NAND \in \mathcal G$.</p></li>
<li><p><strong>Implication-like gates.</strong> Consider the gate $G(x,y) = \neg x \ou y$, which only outputs zero if $(x,y) = (1,0)$. For what follows, a similar analysis will apply for the gate $G'(x,y) = x \ou \neg y$. <br><br>
Consider any string $x \in \{0,1\}^n$.
If $x$ ends in $0$, decompose $x$ into substrings of the form $w_j = 1^\ast 0$; on each such $w_j$, we recursively apply $G$ from the right to the left, which yields output $0$ for each $w_j$. (For a substring of length 1, we use the trivial circuit, i.e. leave that input alone.) Similarly, if $x$ ends in $1$, decompose $x$ into substrings of the form $w_j =0^\ast 1$, and recursively apply $G$ from left to right on each $w_j$, which yields the output $1$ for each $w_j$. Thus we may reduce the problem to building circuits which are satisfied either by $0^m$ or $1^m$, where $m$ is the number of substrings $1^\ast0$ or $0^\ast 1$. For $m \geqslant 2$, we may accept either using $G$ gates by recursively applying $G$ from left to right. This just leaves the case $m = 1$, for which the problematic case are inputs $x \in 1^\ast 0$.<br><br> For $x= 1^\ast 0$, any circuit consisting only of $G$ gates will only yield shorter strings of the form $1^\ast 0$, ultimately yielding the single-bit string $0$: so that no circuit of $G$ gates can be satisfied by this input. If there is <em>also</em> a gate $H \in \mathcal G$ for which $H(1,0) = 1$, then $\{G,H\}$ is tautologous; or, if there is a gate $H \in \mathcal G$ for which $H(1,1) = 0$, we may reduce strings of the form $11^\ast 0$ to strings of the form $(1^\ast 0)^\ast$, by applying $H$ to the first two bits of $x$. Otherwise, no circuit can be constructed which accepts $x \in 1^\ast 0$.<br><br>
Thus, for any gate-set $\mathcal G$ which contains an implication-like gate, <strong>OPSAT</strong> is easy. </p></li>
<li><p><strong>Negations of projections.</strong> Consider the gates $\neg \pi_1(x,y) = \neg x$ and $\neg \pi_2(x,y) = \neg y$. We consider $\neg \pi_1$, the analysis with $\neg \pi_2$ being similar. On its own, $\neg \pi_1$ can  accept any string in $0(0|1)^{n-1}$ for $n \geqslant 2$ by reducing the final $n-1$ bits to a single bit, and then applying $\neg \pi_1$; and it can similarly accept $1(0|1)^{n-1}$ for $n \geqslant 3$ by reducing the final $n-2$ bits to a single bit, and then applying the circuit $\neg \pi_1(\neg \pi_1(x_1, x_2),x_3)$. The only inputs that $\neg \pi_1$ circuits cannot accept are then $10$ or $11$; determining whether any supplemental gate accepts these is trivial. Thus, <strong>OPSAT</strong> is easy for the negations of projections.</p></li>
<li><p><strong>PARITY and EQUALITY</strong>. Consider the gate $\PARITY(x,y) = (x \ou \neg y) \et (\neg x \ou y)$.
The gate set $\mathcal G = \{\PARITY\}$ obviously can only be
satisfied precisely by strings $x \in \{0,1\}^n$ with an odd number
of 1s; we consider the benefit of adding any other gate.</p>

<ul>
<li>Any gate-set which contains both $\PARITY$ and either $\AND$ or
$\NOR(x,y) = \neg(x \ou y)$ can simulate circuits which contain
$\OR$ or $\NAND$ gates (respectively) for fixed inputs, which are
easy cases of <strong>OPSAT</strong>.</li>
<li>Either $\pi_1(x,y) = x$ or $\pi_2(x,y) = y$ can be used to simulate either $\AND$ or $\NOR$ on two-bit substrings of even parity, so that we may reduce gate-sets with these gates and $\PARITY$ to the preceding case.</li>
<li>$\PARITY$ together with $\EQUAL = \neg \PARITY$ is tautologous.</li>
<li>If we supplement $\PARITY$ with the gate $G_{01} = \neg x \et y$, we can accept any even-parity string except for $x \in (11)^\ast 0^\ast$ by applying $G_{01}$ to a $01$-substring of $x$ and then applying a $\PARITY$ circuit to the rest. Similarly, $\PARITY$ together with $G_{10} = x \et \neg y$ can accept any string except those of the form $x \in 0^\ast (11)^\ast$. Supplementing $\PARITY$ with both $G_{01}$ and $G_{10}$ allow us to build circuits which accept all inputs except $x \in 0^\ast$ and $x = 11$.</li>
<li>Finally, if we supplement $\PARITY$ with the constant gate $Z(x,y) = 0$, we can accept any input except for $x \in (11)^\ast$ or $x \in 0^\ast$ by applying a $G$ gate to a substring $01$ or $10$, reducing to the odd parity case.</li>
</ul>

<p>Thus, <strong>OPSAT</strong> is easy for any $\mathcal G$ containing $\PARITY$.<br><br>A similar analysis applies for the $\EQUAL$ gate as for the $\PARITY$ gate: because $\EQUAL(x,y) = \neg \PARITY(x,y) = \neg \PARITY(\neg x, \neg y)$, circuits of $\EQUAL$ gates essentially count the parity of the number of $0$s in the input. We may then reduce the analysis for $\EQUAL$ to that of $\PARITY$ by exchanging $0$ and $1$.</p></li>
<li><p><strong>Projection gates.</strong> The gates $\pi_1(x,y) = x$ and $\pi_2(x,y) = y$, taken on their own, can only build circuits which accept strings starting or ending in $1$, respectively. Consider the effect of augmenting the gate $\pi_1$ with any other gate (a similar analysis holds for $\pi_2$):</p>

<ul>
<li>Allowing both $\pi_1$ and $\pi_2$ allows the construction of a "selection" circuit, which simply outputs any single bit from the input; these can accept any $x \ne 0^n$, and supplementing them with any gate $G$ for which $G(0,0) = 1$ allows a satisfied circuit to be built for any $x$. </li>
<li>If we supplement $\pi_1$ with either $\NOR$ or $G_{01} = \neg x \et y$, we may simulate either $\OR$ or an implication-like gate for fixed inputs; <strong>OPSAT</strong> is solved for both of these cases.</li>
<li>If we supplement $\pi_1$ with either $\AND$, $G_{10} = x \et \neg y$, the constant gate $Z(x,y) = 0$, or any combination of them, we get no additional accepting power, so that we still can only accept strings starting with $1$.</li>
</ul>

<p>Thus, for any other gate we may supplement $\pi_1$ (or $\pi_2$) with, we obtain either a tautologous set, obtain no additional accepting power over just $\pi_1$ (or $\pi_2$), or may reduce to an earlier easy case of <strong>OPSAT</strong>. Then any instance of <strong>OPSAT</strong> with $\pi_1 \in \mathcal G$ or $\pi_2 \in \mathcal G$ is easy.</p></li>
<li><p><strong>Delta-function gates.</strong> Consider the two-bit gates for which there is only one input which satisfies them: $\AND$, $\NOR$, $G_{10}(x,y) = x \et \neg y$, and $G_{01}(x,y) = \neg x \et y$. Circuits made only with $\AND$ gates can only accept the string $1^\ast$: supplementing them with any other delta-function  gate allows them to simulate either $\EQUAL$, $\pi_1$, or $\pi_2$, which are solved cases; similar remarks apply to $\NOR$.
As well, the gate-set $\{G_{01}, G_{10}\}$ can be used to also simulate the $\PARITY$ gate. We may thus focus on either the gate $G_{10}$ or $G_{01}$, possibly supplemented with the gate $Z(x,y) = 0$. We focus on $G_{10}$, with the case of $G_{01}$ being similar.<br><br>Circuits made of $G_{10}$ alone can be built to accept $1(0|1)^{n-1}$, except for the string $11$, by applying an arbitrary circuit to the final $n-2$ bits and then applying the circuit $G_{10}(x_1, G_{10}(x_2, x_3))$. Clearly, the string $11$ can't be accepted by $G_{10}$ or by $Z$; and we can show by induction that any $G_{10}$ circuit which accepts a string must have intermediate outcomes of the gates in the left-most branch all yielding $1$, up to the left-most input itself. No additional benefit is obtained by adding $Z$ gates. Therefore, $G_{10}$ circuits can only accept $x \in 1(0|10|11)(0|1)^\ast$. </p></li>
<li><p>Finally, circuits composed only of $Z$ gates accept no inputs.</p></li>
</ol>

<p>As each gate gives rise to a well-defined and generally quite large class of inputs which it accepts, with additional gates tending to trivialize the problem, we find that <strong>2-TREE-OPSAT</strong> is in <strong>P</strong>.</p>

CC BY-SA 3.0
2012-08-14T17:50:22.347Z
@DSounders: with respect to your recent revision of the problem to determine if there is a circuit $C$ which maps $x$ to some *target value* $b \in \{0,1\}$, rather than just the special case $b = 1$, the same analysis as in my present answer still suffices to show that the problem is in **P**; only the roles of the gates change. For instance, in interchanging the desired outcomes $0$ and $1$, we effectively interchange the roles of **AND** and **OR**, **NAND** and **NOR**, the implication-like gates with the other delta-functions, *etc.*
Niel de Beaudrap
CC BY-SA 3.0
2012-08-14T14:10:20.567Z
2012-08-14T23:13:20.253Z
2012-08-14T23:13:20.253Z
Niel de Beaudrap
<p>This is similar to SAT, except that we know the assignment of each variable, but do not know the assignment of any boolean operator. In that case, is finding the assignment of each operator so the expression evaluates to a given boolean value a NPC problem? </p>

<p>Actually, I was wondering if finding assignment of arithmetic operators to satisfy an integer arithmetic expression(e.g., $1$ $op_1$ $3$ $op_2$ $7$ $op_3$ $op_4$ = 10) is NP complete?</p>

CC BY-SA 3.0
2012-08-12T04:05:48.660Z
So, if I understood correctly, you know that the formula is satisfiable and you want to know an assignment of the boolean operators. Just assign the $\vee$ operator to all "operator variables" and you are done. I don't know about the second problem, but it looks interesting.
George
CC BY-SA 3.0
2012-08-12T07:31:03.117Z
@GeorgeB: I don't think that solution is correct. What if all of the Boolean values are set to false? This question is interesting, but may need a bit of work. What set of Boolean operators are we choosing from? Presumably you mean an interesting subset of binary Boolean operators like $\{ \lor, \land, \Leftrightarrow \}$. If you include all binary Boolean operators, then the problem is trivial - just pick the constant map to 'true'.
Huck Bennett
CC BY-SA 3.0
2012-08-12T11:31:52.493Z
As Huck said, pick $x \mathop{op_i} y = 1$ for all $i$. However if you restrict the operators to a particular set then the question would be more interesting. Similarly for arithmetic case.
Kaveh
CC BY-SA 3.0
2012-08-12T15:42:45.600Z
this seems like it might have some connection to QBFs or possibly reduced to it. probably a QBF can be constructed that when solved, gives the operators. right? on fast inspection it looks like it could be Pspace complete... also you have to define precedence if there are no parentheses. AND higher than OR? the problem seems more natural maybe when parenthesis/groupings can be defined.
vzn
CC BY-SA 3.0
2012-08-13T18:41:57.827Z
@GeorgeB. I'm sorry I didn't make it clear. The evaluation of a boolean expression can be any given boolean value, either 0 or 1.
DSounders
<cc.complexity-theory><np-hardness>
Is the problem of finding operators to satisfy a list of boolean variables NP complete?
DSounders
# Is the problem of finding operators to satisfy a list of boolean variables NP complete?

(Asked by: username_0 on 2012-08-12)

This is similar to SAT, except that we know the assignment of each variable, but do not know the assignment of any boolean operator. In that case, is finding the assignment of each operator so the expression evaluates to a given boolean value a NPC problem?

Actually, I was wondering if finding assignment of arithmetic operators to satisfy an integer arithmetic expression(e.g., $1$ $op\_1$ $3$ $op\_2$ $7$ $op\_3$ $op\_4$ = 10) is NP complete?

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: So, if I understood correctly, you know that the formula is satisfiable and you want to know an assignment of the boolean operators. Just assign the $\vee$ operator to all "operator variables" and you are done. I don't know about the second problem, but it looks interesting.  
> **username_2**: @username_1B: I don't think that solution is correct. What if all of the Boolean values are set to false? This question is interesting, but may need a bit of work. What set of Boolean operators are we choosing from? Presumably you mean an interesting subset of binary Boolean operators like $\{ \lor, \land, \Leftrightarrow \}$. If you include all binary Boolean operators, then the problem is trivial - just pick the constant map to 'true'.  
> **username_3**: As Huck said, pick $x \mathop{op_i} y = 1$ for all $i$. However if you restrict the operators to a particular set then the question would be more interesting. Similarly for arithmetic case.  
> **username_4**: this seems like it might have some connection to QBFs or possibly reduced to it. probably a QBF can be constructed that when solved, gives the operators. right? on fast inspection it looks like it could be Pspace complete... also you have to define precedence if there are no parentheses. AND higher than OR? the problem seems more natural maybe when parenthesis/groupings can be defined.  
> **username_0**: @username_1B. I'm sorry I didn't make it clear. The evaluation of a boolean expression can be any given boolean value, either 0 or 1.  

---

## 2 answers

### Answer by username_5 on 2012-08-12. Score: 10

With addition and subtraction, I think the [Partition problem](http://en.wikipedia.org/wiki/Partition_problem), which is NP-hard, reduces to your second problem.

Given a set $S = \{s\_1, s\_2, \ldots, s\_n\}$ we create the problem

$s\_1$ $op\_1$ $s\_2$ $op\_2$ $s\_3$ $op\_3$ $\ldots op\_{n-1}$ $s\_n = 0$.

If a solution exists, we create two sets:

$S\_1 = \{s\_1\}\cup \{s\_i | op\_{i-1} = +\}$

$S\_2 = \{s\_i | op\_{i-1} = -\}$

These two sets have to have the same sum by the setup of our original problem, so the partition problem is solved. This shows that not only is coming up with the actual solution to this problem hard, it's in fact NP hard to determine if a solution exists (at least for addition and subtraction).

For a set of operations that doesn't allow creation of negative integers, say multiplication and addition, it's not so clear. Also, this only shows that the problem is weakly NP-hard; there may be a reduction that gives a stronger result than this.

> **Comments:**
> **username_6**: I think your proof can be adapted to the $\times/\div$ case fairly easily, just set the target problem to $s_{1}\ldots s_{n} = 1$. Then a solution implies the denominator is the same as the numerator (assuming $s_{i} > 0$ for all $i$). Of course this doesn't give the four operator case, but then we'd also have to handle order of operations.  
> **username_0**: Thanks, @Sam and Luke. What if we mix all four operators? Intuitively having more operators will only make the problem more complex, but I don't see a straight-forward proof.  
> **username_6**: Still thinking about all four. We can also get $+/\div$ easily, but that's still only two at a time.  
> **username_6**: Also, a reference for the (strong) $NP$-completeness of PRODUCT PARTITION: "“Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation" http://www.sciencedirect.com/science/article/pii/S0377221710003905  

---

### Answer by username_7 on 2012-08-14. Score: 4

**Short answer.** The operator version of **SAT** is efficiently solvable — at least, if we assume arbitrary circuits of two-input gates with no fan-out, over any desired choice of gate-set.

**Long answer.**
I assume the following form of the boolean problem:

> **2-TREE-OPSAT.** Given an input $x \in \{0,1\}^n$ for $n \geqslant 2$ and a gate set $\mathcal G$ consisting of 2-input one-output gates, does there exists a circuit $C$ consisting of gates in $\mathcal G$ which *accepts* $x$, that is, which is satisfied when given the input $x$ (mapping bits of $x$ to the leaves of the circuit $C$ in-order)?

In particular, we impose no particular structure on the circuits $C$ (aside from being binary trees), do not allow fan-out (so that each bit of $x$ is used only once), and the gates may be asymmetric. By allowing only two-bit gates, I exclude the **NOT** gate (but which may be simulated by having multiple gates which are related to each other by negations, such as **AND**/**NAND**; and I also exclude gates that simply output constants with no inputs, so that the number of gates in the circuit will in fact always be $n-1$ for an $n$-bit input. For the sake of brevity, I will refer to **2-TREE-OPSAT** below simply as **OPSAT**; though analysis of the problem may become much more difficult for circuits allowing arbitrary *k*-input gates (**k-TREE-OPSAT**) or allowing fan-out (which we might call **k-FANOUT-OPSAT**).

[*Edited to add*: we can easily adapt this to consider the more general problem of the current revision of your question, in which we attempt to map a given $x \in \{0,1\}^\ast$ to a target value $b \in \{0,1\}$, by interchanging the roles of $0$ and $1$ in the analysis below; this has the effect of interchanging the roles of **AND** and **OR**, **NAND** and **NOR**, *etc.*]
$\def\et{\wedge}\def\ou{\vee}\def\AND{\mathop{\text{AND}}}\def\NAND{\mathop{\text{NAND}}}\def\OR{\mathop{\text{OR}}}\def\NOR{\mathop{\text{NOR}}}\def\EQUAL{\mathop{\text{EQUAL}}}\def\PARITY{\mathop{\text{PARITY}}}$

For a fixed choice of $x \in \{0,1\}^n$, the problem of choosing a suitable tree with suitable gates is not unlike a logical disjunction: using equivalences such as
$$ \OR(x,y) \;\equiv\;\Bigl(\AND(x,y) \;\ou\; \PARITY(x,y)\Bigr) $$
we may perform reductions between collections relating more complicated gate sets to simple (and powerful) gate sets; a may speak of one gate set being able to emulate other gates not belonging to the set, by wisely choosing some element of $\mathcal G$ which has the same effect (when presented with a particular input) as a gate $G \notin \mathcal G$. In particular, certain combinations of gates (such as $\{ \OR, \NAND \}$) can simulate the constant function yielding $1$: we say that such gate-sets are *tautologous*.

We proceed by considering gate sets including different types of gates $G$, later excluding those gates from later cases of the analysis, to show that gate-sets involving any single one of the gates leads to a tractible problem. We will proceed in the order of the number of two-bit strings which satisfy the gate in question, starting from the constant $1$ gate to the constant $0$ gate.

1. For any gate set $\mathcal G$ which contains the constant gate $G(x,y) = 1$, we may simply build a circuit $C$ using that gate alone, in which case $C$ accepts any $x$.
2. **OR and NAND.** For any gate set $\mathcal G$ which contains $\OR$: if all other gates $G \in \mathcal G$ satisfy $G(x,y) \implies \OR(x,y)$, then there is no advantage to choosing any other gate but $\OR$ in building the circuit $C$. A circuit of only $\OR$ gates accepts any string except $x \in 0^\ast$. Otherwise, there exists a gate $G \in \mathcal G$ such that $\{G, \OR\}$ is tautologous. So any instance of **OPSAT** with $\OR \in \mathcal G$ is easy; and similar remarks apply for $\NAND \in \mathcal G$.
3. **Implication-like gates.** Consider the gate $G(x,y) = \neg x \ou y$, which only outputs zero if $(x,y) = (1,0)$. For what follows, a similar analysis will apply for the gate $G'(x,y) = x \ou \neg y$.   
     
   Consider any string $x \in \{0,1\}^n$.
   If $x$ ends in $0$, decompose $x$ into substrings of the form $w\_j = 1^\ast 0$; on each such $w\_j$, we recursively apply $G$ from the right to the left, which yields output $0$ for each $w\_j$. (For a substring of length 1, we use the trivial circuit, i.e. leave that input alone.) Similarly, if $x$ ends in $1$, decompose $x$ into substrings of the form $w\_j =0^\ast 1$, and recursively apply $G$ from left to right on each $w\_j$, which yields the output $1$ for each $w\_j$. Thus we may reduce the problem to building circuits which are satisfied either by $0^m$ or $1^m$, where $m$ is the number of substrings $1^\ast0$ or $0^\ast 1$. For $m \geqslant 2$, we may accept either using $G$ gates by recursively applying $G$ from left to right. This just leaves the case $m = 1$, for which the problematic case are inputs $x \in 1^\ast 0$.  
     
    For $x= 1^\ast 0$, any circuit consisting only of $G$ gates will only yield shorter strings of the form $1^\ast 0$, ultimately yielding the single-bit string $0$: so that no circuit of $G$ gates can be satisfied by this input. If there is *also* a gate $H \in \mathcal G$ for which $H(1,0) = 1$, then $\{G,H\}$ is tautologous; or, if there is a gate $H \in \mathcal G$ for which $H(1,1) = 0$, we may reduce strings of the form $11^\ast 0$ to strings of the form $(1^\ast 0)^\ast$, by applying $H$ to the first two bits of $x$. Otherwise, no circuit can be constructed which accepts $x \in 1^\ast 0$.  
     
   Thus, for any gate-set $\mathcal G$ which contains an implication-like gate, **OPSAT** is easy.
4. **Negations of projections.** Consider the gates $\neg \pi\_1(x,y) = \neg x$ and $\neg \pi\_2(x,y) = \neg y$. We consider $\neg \pi\_1$, the analysis with $\neg \pi\_2$ being similar. On its own, $\neg \pi\_1$ can accept any string in $0(0|1)^{n-1}$ for $n \geqslant 2$ by reducing the final $n-1$ bits to a single bit, and then applying $\neg \pi\_1$; and it can similarly accept $1(0|1)^{n-1}$ for $n \geqslant 3$ by reducing the final $n-2$ bits to a single bit, and then applying the circuit $\neg \pi\_1(\neg \pi\_1(x\_1, x\_2),x\_3)$. The only inputs that $\neg \pi\_1$ circuits cannot accept are then $10$ or $11$; determining whether any supplemental gate accepts these is trivial. Thus, **OPSAT** is easy for the negations of projections.
5. **PARITY and EQUALITY**. Consider the gate $\PARITY(x,y) = (x \ou \neg y) \et (\neg x \ou y)$.
   The gate set $\mathcal G = \{\PARITY\}$ obviously can only be
   satisfied precisely by strings $x \in \{0,1\}^n$ with an odd number
   of 1s; we consider the benefit of adding any other gate.

   * Any gate-set which contains both $\PARITY$ and either $\AND$ or
     $\NOR(x,y) = \neg(x \ou y)$ can simulate circuits which contain
     $\OR$ or $\NAND$ gates (respectively) for fixed inputs, which are
     easy cases of **OPSAT**.
   * Either $\pi\_1(x,y) = x$ or $\pi\_2(x,y) = y$ can be used to simulate either $\AND$ or $\NOR$ on two-bit substrings of even parity, so that we may reduce gate-sets with these gates and $\PARITY$ to the preceding case.
   * $\PARITY$ together with $\EQUAL = \neg \PARITY$ is tautologous.
   * If we supplement $\PARITY$ with the gate $G\_{01} = \neg x \et y$, we can accept any even-parity string except for $x \in (11)^\ast 0^\ast$ by applying $G\_{01}$ to a $01$-substring of $x$ and then applying a $\PARITY$ circuit to the rest. Similarly, $\PARITY$ together with $G\_{10} = x \et \neg y$ can accept any string except those of the form $x \in 0^\ast (11)^\ast$. Supplementing $\PARITY$ with both $G\_{01}$ and $G\_{10}$ allow us to build circuits which accept all inputs except $x \in 0^\ast$ and $x = 11$.
   * Finally, if we supplement $\PARITY$ with the constant gate $Z(x,y) = 0$, we can accept any input except for $x \in (11)^\ast$ or $x \in 0^\ast$ by applying a $G$ gate to a substring $01$ or $10$, reducing to the odd parity case.

   Thus, **OPSAT** is easy for any $\mathcal G$ containing $\PARITY$.  
     
   A similar analysis applies for the $\EQUAL$ gate as for the $\PARITY$ gate: because $\EQUAL(x,y) = \neg \PARITY(x,y) = \neg \PARITY(\neg x, \neg y)$, circuits of $\EQUAL$ gates essentially count the parity of the number of $0$s in the input. We may then reduce the analysis for $\EQUAL$ to that of $\PARITY$ by exchanging $0$ and $1$.
6. **Projection gates.** The gates $\pi\_1(x,y) = x$ and $\pi\_2(x,y) = y$, taken on their own, can only build circuits which accept strings starting or ending in $1$, respectively. Consider the effect of augmenting the gate $\pi\_1$ with any other gate (a similar analysis holds for $\pi\_2$):

   * Allowing both $\pi\_1$ and $\pi\_2$ allows the construction of a "selection" circuit, which simply outputs any single bit from the input; these can accept any $x \ne 0^n$, and supplementing them with any gate $G$ for which $G(0,0) = 1$ allows a satisfied circuit to be built for any $x$.
   * If we supplement $\pi\_1$ with either $\NOR$ or $G\_{01} = \neg x \et y$, we may simulate either $\OR$ or an implication-like gate for fixed inputs; **OPSAT** is solved for both of these cases.
   * If we supplement $\pi\_1$ with either $\AND$, $G\_{10} = x \et \neg y$, the constant gate $Z(x,y) = 0$, or any combination of them, we get no additional accepting power, so that we still can only accept strings starting with $1$.

   Thus, for any other gate we may supplement $\pi\_1$ (or $\pi\_2$) with, we obtain either a tautologous set, obtain no additional accepting power over just $\pi\_1$ (or $\pi\_2$), or may reduce to an earlier easy case of **OPSAT**. Then any instance of **OPSAT** with $\pi\_1 \in \mathcal G$ or $\pi\_2 \in \mathcal G$ is easy.
7. **Delta-function gates.** Consider the two-bit gates for which there is only one input which satisfies them: $\AND$, $\NOR$, $G\_{10}(x,y) = x \et \neg y$, and $G\_{01}(x,y) = \neg x \et y$. Circuits made only with $\AND$ gates can only accept the string $1^\ast$: supplementing them with any other delta-function gate allows them to simulate either $\EQUAL$, $\pi\_1$, or $\pi\_2$, which are solved cases; similar remarks apply to $\NOR$.
   As well, the gate-set $\{G\_{01}, G\_{10}\}$ can be used to also simulate the $\PARITY$ gate. We may thus focus on either the gate $G\_{10}$ or $G\_{01}$, possibly supplemented with the gate $Z(x,y) = 0$. We focus on $G\_{10}$, with the case of $G\_{01}$ being similar.  
     
   Circuits made of $G\_{10}$ alone can be built to accept $1(0|1)^{n-1}$, except for the string $11$, by applying an arbitrary circuit to the final $n-2$ bits and then applying the circuit $G\_{10}(x\_1, G\_{10}(x\_2, x\_3))$. Clearly, the string $11$ can't be accepted by $G\_{10}$ or by $Z$; and we can show by induction that any $G\_{10}$ circuit which accepts a string must have intermediate outcomes of the gates in the left-most branch all yielding $1$, up to the left-most input itself. No additional benefit is obtained by adding $Z$ gates. Therefore, $G\_{10}$ circuits can only accept $x \in 1(0|10|11)(0|1)^\ast$.
8. Finally, circuits composed only of $Z$ gates accept no inputs.

As each gate gives rise to a well-defined and generally quite large class of inputs which it accepts, with additional gates tending to trivialize the problem, we find that **2-TREE-OPSAT** is in **P**.

> **Comments:**
> **username_7**: @username_0: with respect to your recent revision of the problem to determine if there is a circuit $C$ which maps $x$ to some *target value* $b \in \{0,1\}$, rather than just the special case $b = 1$, the same analysis as in my present answer still suffices to show that the problem is in **P**; only the roles of the gates change. For instance, in interchanging the desired outcomes $0$ and $1$, we effectively interchange the roles of **AND** and **OR**, **NAND** and **NOR**, the implication-like gates with the other delta-functions, *etc.*  

---

