Hardness of this problem

Hi, I'm trying to determine the complexity of the following problem.

I have O(N) boolean formulas each with O(log N) distinct variables.
Additionally, the number of boolean variables total is O(N).

Also, create an arbitrary ordering for each state of the O(N) boolean
variables.

Create a vector, Vk, for each formula and its element i to 1 if the formula
is true when the variables are in state i and -1 otherwise. So, each vector
will be size O(2^N).

Example:
Consider <A and B> and <A>
<A and B> corresponds to {1, -1, -1, -1}.
<A> corresponds to {1, 1, -1, -1 }

Additionally define a pickable nonnegative Qk for each vector (they can be
fractional).
(also assume Q1 >= 1)

Define W to be the sum of Qk*Vk for all k formulas.

The problem is to determine if there is a selection of Qk's such that W is
nonpositive in all possible states.

Example:
The formulas are: <A and B> <not A>.
So the vectors are: V1 = {1, -1, -1, -1} and V2 = {-1, -1, 1, 1}
Choose Q1 = 1 and Q2 = 1.
Our W is now: {0, -2, 0, 0} which is OK. So Q1 = Q2 = 1 works.

Note that you don't have to compute any of the vectors explicitly. You can
work with just the boolean formulas. Otherwise it would definitely make the
problem intractable.

Relaxing the problem to allow O(N) variables per formula makes it coNPhard.
Use one formula and there is a selection iff the formula you used is
unsatisfiable.
(because unsatisfiable -> all negative states the vector)

Restricting to log N total variables makes each vector size N and it is in
P.

With O(log N) variables per formula but O(N) total variables is the problem
hard?

Thanks,
Scott



.