From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,9dfc10efb95ba130 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news2.google.com!news4.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Niklas Holsti Newsgroups: comp.lang.ada Subject: Re: Inefficient algorithms Date: Sat, 11 Sep 2010 18:05:51 +0300 Organization: Tidorum Ltd Message-ID: <8f1k6gFgkrU1@mid.individual.net> References: <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com> <8f0nd6F8ucU1@mid.individual.net> <8f0o4uFct8U1@mid.individual.net> <0ce6d303-c8ff-4688-8372-00238f52d1d4@s24g2000pri.googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net aXVGkAvzEk1RcNBNesQZygf2OoVDVDHE+6aLkub09PP8V9H/+e Cancel-Lock: sha1:r27a2eoRhXHf43tk3o5sdvCalXo= User-Agent: Mozilla-Thunderbird 2.0.0.24 (X11/20100328) In-Reply-To: <0ce6d303-c8ff-4688-8372-00238f52d1d4@s24g2000pri.googlegroups.com> Xref: g2news1.google.com comp.lang.ada:14015 Date: 2010-09-11T18:05:51+03:00 List-Id: Rick wrote: > On Sep 11, 3:07 pm, Niklas Holsti > wrote: >> Niklas Holsti wrote: >>> Rick wrote: >>>> I am working on a class in algorithmic efficiency and, to make a >>>> point, need an algorithm that runs O(2^n) - a factoring algorithm >>>> perhaps. All I can find is 'C' code I can't decipher. Can someone >>>> please help with an Ada example. >>> Perhaps the canonical example is this: you are given a Boolean formula >>> containing n Boolean variables. Find a valuation (a value, True or >>> False, for each variable) that makes the formula True. >> Replying to myself, since I realize that I probably misunderstood your >> need: what you want is an inefficient O(2^n) solution to an easy >> (non-exponential) problem. The problem I suggested is not, of course, an >> easy one. But it has easy variants. For example, require that the >> Boolean formula uses at most 10 of the n variables, where this limit >> (10) is considered a fixed number independent of the total number (n) of >> variables. >> >> -- >> Niklas Holsti >> Tidorum Ltd >> niklas holsti tidorum fi >> . @ . > > I must be a bit daft, Niklas, but I don't get it. > What sort of a Boolean formula are you talking about? For example, in Ada, with N = 4: type Bool_Valuation is array (1 .. 4) of Boolean; function Formula (Input : Bool_Valuation) return Boolean is begin return Input(1) and Input(2) /= Input (4) and (Input(3) or (Input(1) and Input(4))) and (Input(2) /= Input(1)); end Formula; The problem is to find some value of the Input parameter (that is, 4 Boolean values, one each for Input(1), Input(2), Input(3), and Input(4)) such that Formula (Input) returns True. One solution is (True, False, False, True). In real applications of the Boolean satisfiability problem, the number of variables can be huge (thousands or millions, I believe -- it keeps increasing year by year). In real applications the Formula would typically not be written out in Ada, as in the above example, but would be given as input to the program and represented by some data structure. The brute-force exponential algorithm is to try all possible values of the Input parameter. There are 2**4 = 16 such values in the example. > How do I use it in a recursive function? The recursion is just used to enumerate (go through) all possible values of the Input parameter when (as in the general case) the length of the Input vector is some variable N. The idea is to first enumerate all values of Input where Input(1) = False, and then (if no solution was found yet) enumerate all values of Input where Input(1) = True. To enumerate all Inputs where Input(1) has a given value, a recursive call is used to enumerate all the values of the rest of the Input, which is Input(2..N). The recursion ends when it is trying a value for Input(N), and then it just calls Formula (Input); if the result is True, this value of Input is a solution. I have placed example Ada code at http://www.tidorum.fi/soldem.zip. But I repeat, this problem is a hard one, for which it is not easy to find more efficient general solutions, unless you know something more about the formula. For example, if you know that it uses at most 10 variables (not all the N variables), you can inspect the formula to find which 10 variables it uses and then limit the search to all the possible values of these 10 variables, giving a constant 2**10 number of choices instead of the general 2**N. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ .