Something boolean before resting

[davv]

And here's something I'm curious about, though I probably shouldn't ask here.

Say F is a boolean statement in disjunctive normal form, and the input boolean values are x_1 ... x_n, and we're also given some k so that 0 < k <= n.

Then, is it possible to describe the boolean function
"exactly k of x_1 ... x_n must be true" AND F

in DNF form without the thing blowing up exponentially? (I suspect not.)

Comments

[goldkin]

Assuming we are given the evaluation of AND F in less than exponential time:

Yes, if k <= 2. Otherwise, no.

[davv]

Hm, perhaps I should clarify a little so I'm sure we mean the same thing.

Let e(x_1...x_n, k) be the exact value function that returns true iff exactly k of the input booleans are on.

Let f(x_1...x_n) be a function that can be expressed as a polynomial length disjunctive normal form statement (with respect to n).

What I then wish to do is to find a satisfiable instance for

e(x_1...x_n, k) AND f(x_1...x_n)

when given k and f(x_1...x_n).

I know that 2-SAT is possible to do in polytime but 3-SAT generally is not (unless you can get a Millennium Prize in the process, or get even more money more clandestinely).

Thus I'm looking at DNF-SAT, which I know is solvable in polytime, however many terms you have in the interior clauses. Luckily for me, the problem that produces f is very easily expressed in DNF form.

So are you saying that it's impossible to combine e() with f() in a way that can be expressed in disjunctive normal form without a worst case exponential explosion of the length of that DNF statement?

Or alternately, can you reduce any sort of DNF statement into a 2-CNF statement, and then combine the thus reduced f() with an e() that has also a max of 2 clauses so as to make the whole thing solvable by 2-CNF-SAT?

-

If you're interested, the actual problem, from where I get f, is this:

You're given a bunch of rules of things that can't go together. E.g. "if you pick object X1, you can't pick object X2 or object X3; if you pick object X2, you can't pick object X1 or X4; ...".

Given those rules, find out how to pick k objects without violating any rules, if this is possible.

The rules can thus be expressed in DNF, like (X1 AND !X2 AND !X3) or (X2 AND !X1 AND !X4) or (...) in the example above. Because each term contains an "if you pick Xp" and one or more "then you can't pick Xq", each of these inner terms can have a maximum of n+1 terms, and there can be a maximum of n of them, thus the whole DNF is polysize.

So if I only had to find some number of objects, where picking those would not violate any of the rules, I'd be set. However, the problem also says "pick k". So that's where the exact value function comes in. And it feels very much like "so close yet so far" if I can't incorporate the exact value function into the statement without an exponential blowup :)