From: rweems@my-dejanews.com
Subject: Boolean function problem
Date: Fri, 15 Jan 1999 20:45:17 GMT
Newsgroups: sci.math,comp.programming,comp.theory
Keywords: Reducing Boolean expressions (for Golomb rulers)
I posted this in sci.math.research, but I've gotten no responses yet; thought
I'd give it a stab in a few other groups...
Given a boolean function of boolean inputs, g, that's expressed as a list of
minterms (a sum of products), does anyone know of (or have any ideas for) an
algorithm that can efficiently find the minimum set of input values that will
cause g to evaluate false (leaving the other inputs as don't cares)?
When I say efficiently, I basically mean better than trying every input by
brute force. Here's an example...
g = p1*p2+p9*p10+p1*p10+p2*p4+p7*p9+p2*p9+p3*p6+p5*p8+p3*p8+p4*p8+p3*p7+
p4*p7+p5*p10+p1*p6+p5*p6+p1*p3*p4+p1*p4*p5+p1*p7*p8+p1*p8*p9+p1*p3*p5+
p1*p3*p9+p1*p5*p9+p1*p5*p7+p2*p3*p5+p2*p5*p7+p2*p6*p8+p2*p8*p10+
p2*p3*p10+p2*p6*p10+p2*p6*p7+p3*p4*p5+p3*p4*p10+p3*p5*p9+p4*p5*p9+
p4*p6*p10+p4*p6*p9+p6*p7*p8+p6*p7*p10+p6*p8*p10+p6*p8*p9+p7*p8*p10
p1...p10 are the inputs. + means logical or, * means logical and.
For this example, p2+p3+p5+p6+p7+p8+p10 = false is one of the optimal
solutions that will result in g = false; p9+p8+p6+p5+p4+p3+p1 = false is the
other one (it's the "mirror image" of the first one). All other solutions
involve more inputs.
If it helps any, I know that g will never contain a complemented term and each
individual minterm (p1*p2 is the first minterm in the above example) will
involve no more than 4 inputs (and no fewer than 2).
Note that one way to solve this is to find g' (the boolean complement of g)
as a list of minterms. Then we want g' = true. The optimal solution would
then simply be a matter of choosing the shortest minterm in g' as true. I'm
pretty sure that finding g' is, in general, at least as difficult as
brute-forcing though.
Randy Weems
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
==============================================================================
From: Lynn Killingbeck
Subject: Re: Boolean function problem
Date: Fri, 15 Jan 1999 16:09:31 -0600
Newsgroups: sci.math,comp.programming,comp.theory
rweems@my-dejanews.com wrote:
[article above -- djr]
I'd use the Karnaugh map, to find a minimal expression for g'. Then,
just find which of the terms has the fewest factors. Intuitively, it
should be the largest block of 1's in g'. And, yes, I have done this in
10 or more dimensions (but, it takes time, quiet, and concentration - at
least for me). Even then, there might be something shorter using XOR or
other basic operations - my background is/was AND/OR/INVERT basis.
Lynn Killingbeck
==============================================================================
From: nollinge@ens-lyon.fr (Nicolas Ollinger)
Subject: Re: Boolean function problem
Date: 16 Jan 1999 09:33:40 GMT
Newsgroups: sci.math,comp.programming,comp.theory
rweems@my-dejanews.com wrote:
:
: Given a boolean function of boolean inputs, g, that's expressed as a list of
: minterms (a sum of products), does anyone know of (or have any ideas for) an
: algorithm that can efficiently find the minimum set of input values that will
: cause g to evaluate false (leaving the other inputs as don't cares)?
(snip)
: Note that one way to solve this is to find g' (the boolean complement of g)
: as a list of minterms. Then we want g' = true. The optimal solution would
: then simply be a matter of choosing the shortest minterm in g' as true. I'm
: pretty sure that finding g' is, in general, at least as difficult as
: brute-forcing though.
Yes, in general, it is "as difficult" as brute-forcing because SAT problem
is an NP-complete problem. Assuming that NP is perhaps different of P, there
is certainly no interesting general case solution. Neither for the case
equivalent to 3-SAT (minterms with 3 variables).
Nicolas.
--
+-------------------------------------------------------------------+
|Nicolas Ollinger -=Nopid=- |
+-------------------------------------------------------------------+
ENS Lyon - Magistere Informatique et Modelisation - 2eme Annee DMI97
Student
---------------------------------------------------------------------
==============================================================================
From: Randy Weems
Subject: Re: Boolean function problem
Date: Sat, 16 Jan 1999 14:13:23 GMT
Newsgroups: sci.math,comp.programming,comp.theory
Nicolas Ollinger wrote:
> rweems@my-dejanews.com wrote:
> :
> : Given a boolean function of boolean inputs, g, that's expressed as a list of
> : minterms (a sum of products), does anyone know of (or have any ideas for) an
> : algorithm that can efficiently find the minimum set of input values that will
> : cause g to evaluate false (leaving the other inputs as don't cares)?
>
> (snip)
>
> : Note that one way to solve this is to find g' (the boolean complement of g)
> : as a list of minterms. Then we want g' = true. The optimal solution would
> : then simply be a matter of choosing the shortest minterm in g' as true. I'm
> : pretty sure that finding g' is, in general, at least as difficult as
> : brute-forcing though.
>
> Yes, in general, it is "as difficult" as brute-forcing because SAT problem
> is an NP-complete problem. Assuming that NP is perhaps different of P, there
> is certainly no interesting general case solution. Neither for the case
> equivalent to 3-SAT (minterms with 3 variables).
>
When you say SAT, is that the boolean satisfiability problem? I know that problem
is NP-complete, but since I know that no input will ever be complemented,
satisfying (finding the inputs that will make the function false in my case) is
trivial: choose all inputs as false and the function is false. And I know by
experimentation, there's a simple algorithm that will give "good" (but not
necessarily optimal) results: choose the input that occurs the most frequently in
the function as false; re-evaluate the function (thus eliminating all the terms
that contained that input). Repeat this until all terms are gone. You'll be left
with a handful of inputs that you haven't chosen as false, but with the inputs you
have chosen as false, you're guaranteed that g will be false.
Some people in sci.math.research have responded that this problem is equivalent to
minimal set covering of a hypergraph which is NP-complete. That makes sense;
minterms are really just sets. I want the smallest set whose union with every
minterm in g is not null. I'm still holding out hope that my particular g's are of
a form that allows an easier technique for solving.
Randy Weems
==============================================================================
From: "Dan"
Subject: Re: Boolean function problem
Date: Sun, 17 Jan 1999 02:44:50 -0800
Newsgroups: sci.math,comp.programming,comp.theory
Here are the 45 distinct assignments to
your boolean expression. They all make
the expression false (or satisfy the complement).
I used my program twiddle (the earlier version was
named orb) to compute them. The program is available,
but I'm not sure how much money to charge for it yet.
Twiddle has several neat features, including
counting how many solutions there are to a cnf.
Using a component technique, it has counted
upwards of a google (10^100) of solutions to some
expressions, but please note that was a special
case. And while some easy problems with
50,000 variables have been run in 2 minutes, some
problems with just 500 variables take a very long time.
So your mileage may vary.
More advertising later. If you are interested, please send
me email. jdp@isni.net
>For this example, p2+p3+p5+p6+p7+p8+p10 = false is one of the optimal
>solutions that will result in g = false; p9+p8+p6+p5+p4+p3+p1 = false is
the
If I understand you correctly, then p1+p2+p5+p6+p7+p8+p10=false
and p1+p3+p4+p5+p6+p9+p10=false are the other optimal solutions.
If it is a hot item, I could add minimal(maximal) satisfying assignment
as an option to twiddle.
1234567890
----------
0000000000
0000000010
0001000000
0001000010
1000000000
1001000000
1000000010
1001000010
0010000000
0011000000
0010000010
0011000010
1010000000
0000000001
0001000001
0010000001
0000000100
0000000110
1000000100
0000000101
0100000000
0110000000
0100000100
0100000001
0000001000
0100001000
0000001100
0100001100
0000001001
0100001001
1000001000
0000100000
0100100000
0001100000
0000101000
0000100010
1000100000
0010100000
0000010000
0100010000
0001010000
0000011000
0000010010
0000010100
0000010001
rweems@my-dejanews.com wrote in message <77o9cq$thi$1@nnrp1.dejanews.com>...
>I posted this in sci.math.research, but I've gotten no responses yet;
[rest of original snipped -- djr]
==============================================================================
From: Steven Pigeon
Subject: Re: Boolean function problem
Date: Sun, 17 Jan 1999 21:03:00 -0500
Newsgroups: sci.math,comp.programming,comp.theory
Dan wrote:
> Here are the 45 distinct assignments to
> your boolean expression. They all make
> the expression false (or satisfy the complement).
Some are supernumerary; some are masked by others.
A minterm like 'abc' is useless when you also have a 'bc'
minterm. Some pairs:
0011000000
0011000010
0000001001
0100001001
There are some others. I don't feel like comparing all
pairs... :-) .
The first step would be, before any real optimization,
to remove 'masked' minterms.
since 0000001001+0100001001 = 0000001001( 'true' + 0100000000) => 0000001001.
That sets '0100000000' to 'dont care'.
So I thought up this algorithm:
simplify(list)
repeat
//find all masked minterms and slay them ( worst case, O(n^2)).
find the longuest and most common prefix (worst case, O(n^2))
{
build a list with all minterms with that prefix
factor all terms, create a new sublist ( O(n))
simplify(sublist)
find all other heuristic simplifications (**)
reinsert sublist into mainlist
}
until nothing has been done at all.
(**) simplifications like replacing !a && b || a && !b for a ^ b, etc.
Whatever simplifications you can get by adding more operators than
&& and ||, like xor, nand, etc.
The factorisation is simply:
abd + abe + abf = ab(d+e+f).
If a minterm is a prefix, then you have:
ab + abe + abf = ab( 1 + e + f ) = ab
which solves the problem about 'masked' minterms.
This is a polynomial time heuristic simplification, it might not
find all simplifications, and maybe not the optimal simplification,
but at least it is a good start.
Best,
S.
> Twiddle has several neat features, including
> counting how many solutions there are to a cnf.
> Using a component technique, it has counted
> upwards of a google (10^100) of solutions to some
> expressions, but please note that was a special
> case. And while some easy problems with
> 50,000 variables have been run in 2 minutes, some
> problems with just 500 variables take a very long time.
> So your mileage may vary.
well, there are 2^2^n functions of n variables... 10^100must be pretty easy to
hit.
[previous list of 45 sequences deleted --- djr]
----------------------------------------------------------
Steven Pigeon Ph. D. Student.
University of Montreal.
pigeon@iro.umontreal.ca Topics: data compression,
pigeons@jsp.umontreal.ca signal processing,
steven@research.att.com non stationnary signals
and wavelets.
----------------------------------------------------------
http://www.iro.umontreal.ca/~pigeon
==============================================================================
From: Randy Weems
Subject: Re: Boolean function problem
Date: Mon, 18 Jan 1999 22:53:27 GMT
Newsgroups: sci.math,comp.programming,comp.theory
Matt Timmermans wrote:
> You want to set as many inputs as you can to true, while keeping g false,
> i.e., keeping ~g true. Writing ~g in CNF, ie., ~(p1*p2+p3*p4) =
> (~p1+~p2)*(~p3+~p4), shows this to be exactly equivalent to MAX-SAT, and so
> it is NP-complete, even when you reduce all of your clauses to only 2
> variables and disallow any positive terms in ~g.
Is MAX-SAT the same as SAT (the boolean satisfiability problem)? From my
reading of
http://www.nada.kth.se/~viggo/wwwcompendium/node222.html, MAX-SAT appears to
be what I understand as the plain vanilla boolean satisfiability problem.
Finding a set of inputs that will cause my example g to evaluate false (or g'
to evaluate true), is trivial for this problem because there are no negated
(complemented) terms in g.
Now, minimum hitting set
(http://www.nada.kth.se/~viggo/wwwcompendium/node147.html), which is
equivalent to minimum set cover, appears to me to be exactly my problem. And
it's NP-complete (sigh).
Suppose one were to reduce problem A to problem B, and problem B is known to
be NP-complete. Am I correct in believing that this does not necessarily mean
that problem A is NP-complete? If you go the other way around...reduce problem
B to problem A and know that problem B is NP-complete, then problem A is
NP-complete, right?
To shed a little light on this particular problem, the example function I gave
is directly related to golomb rulers of length 11; if g evaluates false, you
have a legal golomb ruler of length 11. Find the maximal number of true inputs
(and minimal number of false inputs) that will cause g to evaluate false, and
you've done the equivalent of place the maximal number of marks on a golomb
ruler of length 11. Take one of the solutions I gave: p2+p3+p5+p6+p7+p8+p10 =
false. This leaves use free to set p1*p4*p9 = true. p0 and p11 are the end
marks of the golomb ruler (i.e. know to be true). p1, p4, and p9 correspond to
the interior marks.
I've written an algorithm that will, given a ruler length, generate the
corresponding g for that ruler length. Just because finding an optimal
solution that will cause g to evaluate false is, in general, NP-complete, that
does not necessarily mean that finding optimal golomb rulers is NP-complete,
right?
Randy Weems
==============================================================================
From: "Matt Timmermans"
Subject: Re: Boolean function problem
Date: Tue, 19 Jan 1999 12:01:30 -0500
Newsgroups: sci.math,comp.programming,comp.theory
Randy Weems wrote in message <36A3BE4E.AEC13F0C@hotmail.com>...
>Matt Timmermans wrote:
>
>> You want to set as many inputs as you can to true, while keeping g false,
>> i.e., keeping ~g true. Writing ~g in CNF, ie., ~(p1*p2+p3*p4) =
>> (~p1+~p2)*(~p3+~p4), shows this to be exactly equivalent to MAX-SAT, and so
>> it is NP-complete, even when you reduce all of your clauses to only 2
>> variables and disallow any positive terms in ~g.
>
>Is MAX-SAT the same as SAT (the boolean satisfiability problem)? From my
>reading of
>http://www.nada.kth.se/~viggo/wwwcompendium/node222.html, MAX-SAT appears to
>be what I understand as the plain vanilla boolean satisfiability problem.
A SAT problem asks "Is this formula satisfiable?", and a MAX-SAT problem
asks "Is this formula satisfiable with at least K variables set true?".
Obviously, if you can answer a MAX-SAT in P, then you can find the maximum
number of true variables in P, and MAX-SAT is only worded as a decision
problem to make it NP.
MAX-SAT is known to remain NP-complete even when all the terms are negative
and all clauses are of length 2, even though 2-SAT can be solved in linear
time.
>Finding a set of inputs that will cause my example g to evaluate false (or g'
>to evaluate true), is trivial for this problem because there are no negated
>(complemented) terms in g.
>
>Now, minimum hitting set
>(http://www.nada.kth.se/~viggo/wwwcompendium/node147.html), which is
>equivalent to minimum set cover, appears to me to be exactly my problem. And
>it's NP-complete (sigh).
That one is also exactly your problem.
>Suppose one were to reduce problem A to problem B, and problem B is known to
>be NP-complete. Am I correct in believing that this does not necessarily mean
>that problem A is NP-complete? If you go the other way around...reduce problem
>B to problem A and know that problem B is NP-complete, then problem A is
>NP-complete, right?
Correct. (Well, technically, it makes A NP-hard. If A is in NP, then it is
NP-complete.)
>I've written an algorithm that will, given a ruler length, generate the
>corresponding g for that ruler length. Just because finding an optimal
>solution that will cause g to evaluate false is, in general, NP-complete, that
>does not necessarily mean that finding optimal golomb rulers is NP-complete,
>right?
Correct. But I do believe that finding the maximum number of marks on a
golomb ruler of a given length is also known to be NP-complete. Sorry, I
have only a vague memory -- no references.