Re: Inefficient algorithms

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

Ludovic Brenta wrote:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>> 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.
> 
> Actually I do think that the problem is trivial and that you can solve
> it without recursion.  If you see your array of Booleans as a number in
> binary representation:
> 
> procedure Inefficient (N : in Natural) is
> 
>    subtype Valuation is Natural range 1 .. 2**N;

That will of course fail to compile when N grows large enough, as it 
will when we are talking of order-of-complexity questions. (Also, I 
think you really wanted the range 0 .. 2**N - 1, giving the N-bit binary 
numbers).

>    -- We assume the solution is Valuation'Last but it could be any value.
>    Solution : constant Valuation := Valuation'Last;
> begin
>    for K in Valuation'Range loop
>       exit when K = Solution;

Here you are assuming that the Boolean formula has the simple form

    Var1 = K1 and Var2 = K2 and Var3 = K3 and ... Var<N> = K<N>

where K1..K<N> are the Boolean constants that correspond to the constant 
bits in your Solution. I had in mind a more general formula where, for 
example, we can compare two variables (Var1 = Var4), negate variables, 
and so on.

In the terms of my first post, this algorithm would be:

    -- The formula for which a solution is sought:

    function Formula (Input : Valuation) return Boolean
    is begin
       return <a complex Boolean formula depending on the N bits
               in the Input parameter>;
    end Formula;

    -- The search for the solution:

    for K in Valuation loop
       exit when Formula (K);
    end loop;

A trivial amount of code, indeed, but since Valuation has 2**N values, 
the loop will iterate 2**N times, so this algorithm is also O(2**N), as 
for the recursive one.

This example is just the Boolean satisfiability problem (SAT), a 
well-known difficult problem, which is not trivial in the general case.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .