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.