Re: Inefficient algorithms

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

Rick wrote:
> On Sep 11, 3:07 pm, Niklas Holsti <niklas.hol...@tidorum.invalid>
> 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
       .      @       .