2
$\begingroup$

I have a set of expressions $E_1 .. E_n$ over boolean variables and I'm looking for an assignment to the variables so that all expressions are satisfied. Normally this would be NP-complete, but I found two particular properties over the set and I'm looking to combine and exploit them.

The idea I have is based on gaussian matrix elimination. In matrix elimination, you take a nonzero column and a row and use them to sweep the column from all other rows. Even for an integer matrix solution, you can find a solution in such a way if the number of rows is about the same as the number of columns and the matrix has exactly 1 solution. In my particular application, I have about as many variables as expressions and in some cases there is only 1 solution and the expressions do not imply each other. (property 1).

I take $E_1$ and one of it's variables. I combine $E_1$ with $E_2$ only if $E_2$ contains that variable. If so, I eliminate the variable from $E_2$ and I will (deterministically but somewhat arbitrarily) eliminate some more variables from $E_2$ that are both in $E_1$ and $E_2$. I keep the expressions as a truth table. Suppose for example that I want to eliminate a, b and c, $E_2$ would become

E_2 = 
    (substitute/a,b,c/0,0,0 (E_1 && E_2)) ||
    (substitute/a,b,c/0,0,1 (E_1 && E_2)) ||
    (substitute/a,b,c/0,1,0 (E_1 && E_2)) ||
    ...
    (substitute/a,b,c/1,1,1 (E_1 && E_2))

$E_2$ may take over some new variables from $E_1$. I would then combine $E_1$ and $E_3$ in the same way until $E_1$ with $E_n$ and then I'd start with $E_2$ with $E_3$ .. $E_n$ etc. at the end, $E_n$ will be an expression in a single variable. Normally this can lead to an exponential blowup for the size of an expression, but in my particular application, I found that because of variables are eliminated, $E_i$ && $E_k$ never has more than 39 variables (Property 2). Truth tables in 39 variables are still feasible.

Unfortunately, unlike matrix gaussian sweep, when substituting the variables, I lose information. For example, if $E_1 = a \rightarrow b$ and $E_2 = b \rightarrow c$ and I'm sweeping with $E_1:b$. $E_2$ would become $E_2 = a \rightarrow c$. Before the sweep, $a,b,c = 0,1,0$ was not a valid assignment, while after the sweep it is valid.

I'm not sure if this limitation can be overcome. Perhaps I should remember the original $E_2 = b \rightarrow c$ in a side-set of expressions, but then how to combine all the expressions in the side set? Or can I perhaps add $c$ to $E_1$, but then Property 2 won't hold anymore? Is there some 3rd property I should look for in my set of expressions, so that this method would work?

Truth table example

The truth table for $E_1 = a \rightarrow b$ (used above) is:

E_1 =
-------------
|a|b|allowed|
-------------
|0|0|    1  |
|0|1|    1  |
|1|0|    0  |
|1|1|    1  |
-------------

A truth table can express any boolean expression (or function) and the size is exponential in the number of variables.

$\endgroup$
5
  • 1
    $\begingroup$ I don't understand what you're doing, or what problem you're solving. What kinds of expressions can each $E_i$ take? Are those arbitrary boolean formulas (with an arbitrary number of variables and any number of disjunctions, conjunctions, and negations, possibly nested)? I don't understand how you are combining $E_1$ with $E_2$. What does it mean to "eliminate" a variable from an expression? Can you be more precise, and maybe also give a few simple examples to illustrate your ideas? Are you familiar with resolution? Have you tried using a SAT solver? $\endgroup$
    – D.W.
    Mar 5, 2017 at 3:00
  • $\begingroup$ Is my example in the gray block where I combine $E_1$ and $E_2$ while eliminating three variables unclear? Initially, $E_i$ are all truth tables with 4 variables max. They cannot be arbitrary formula's, but let's assume for now. When sweeping in the mentioned way, it appears that any $E_i$ && $E_k$ will have a limited number of variables (this limit is now reduced to 23). It follows also that $E_i$ will never have more than 23 variables if applied this way. SAT-solvers cannot solve this as it would crack SHA-2. $\endgroup$ Mar 5, 2017 at 13:27
  • $\begingroup$ I don't understand what an expression is, or what it means to say that an expression $E_i$ is a truth table. (Separately: If solving your problem is at least as hard as cracking SHA-2, solving your problem is probably infeasible.) $\endgroup$
    – D.W.
    Mar 5, 2017 at 13:50
  • $\begingroup$ I expected you would know, but I added an example. There's also a lot on the internet about turning expressions into truth tables. $\endgroup$ Mar 9, 2017 at 5:07
  • $\begingroup$ OK, so an expression is just a logical formula (with any number of variables and any number of disjunctions, conjunctions, and/or negations, possibly nested). So what exactly do you mean by "combining" two expressions? There are many ways one could possibly combine two expressions. What exactly do you mean by "eliminating" a variable from an expression? What do you mean by a "sweep"? Can you edit your question to define your terms? It seems you have some procedure in mind, but I can't decipher what it is. $\endgroup$
    – D.W.
    Mar 12, 2017 at 2:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.