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!news4.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: Inefficient algorithms
Date: Sat, 11 Sep 2010 14:20:09 +0300
Organization: Tidorum Ltd
Message-ID: <8f16vaF2q1U1@mid.individual.net>
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
	<8f0nd6F8ucU1@mid.individual.net> <8f0o4uFct8U1@mid.individual.net>
 <87lj78ab6m.fsf@ludovic-brenta.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net pIDEimjZAiT/0XrDxHQxbwCrZCurgPFGxfIUq5dND70ws9RuWq
Cancel-Lock: sha1:aWSZrOMJ8pT2BmC0FneLRDBRkMg=
User-Agent: Mozilla-Thunderbird 2.0.0.24 (X11/20100328)
In-Reply-To: <87lj78ab6m.fsf@ludovic-brenta.org>
Xref: g2news1.google.com comp.lang.ada:14013
Date: 2010-09-11T14:20:09+03:00
List-Id: <comp.lang.ada>

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
       .      @       .