Is the problem of finding operators to satisfy a list of boolean variables NP complete?
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.