11
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – George Aug 12 '12 at 4:05
  • 3
    $\begingroup$ @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'. $\endgroup$ – Huck Bennett Aug 12 '12 at 7:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Aug 12 '12 at 11:31
  • $\begingroup$ 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. $\endgroup$ – vzn Aug 12 '12 at 15:42
  • $\begingroup$ @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. $\endgroup$ – DSounders Aug 13 '12 at 18:41
10
$\begingroup$

With addition and subtraction, I think the 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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Luke Mathieson Aug 13 '12 at 5:25
  • $\begingroup$ 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. $\endgroup$ – DSounders Aug 14 '12 at 3:01
  • $\begingroup$ Still thinking about all four. We can also get $+/\div$ easily, but that's still only two at a time. $\endgroup$ – Luke Mathieson Aug 14 '12 at 3:49
  • 1
    $\begingroup$ 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" sciencedirect.com/science/article/pii/S0377221710003905 $\endgroup$ – Luke Mathieson Aug 14 '12 at 3:54
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – Niel de Beaudrap Aug 14 '12 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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