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 10:07:09 +0300
Organization: Tidorum Ltd
Message-ID: <8f0o4uFct8U1@mid.individual.net>
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
 <8f0nd6F8ucU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net rTlhu0yMn/qC4ptmnu8rKAjAjXLgvPQdrJ68CPqO8WM0Bwe/OC
Cancel-Lock: sha1:ig6QhKSh+mGWdqsCUOjRJbgwb0c=
User-Agent: Mozilla-Thunderbird 2.0.0.24 (X11/20100328)
In-Reply-To: <8f0nd6F8ucU1@mid.individual.net>
Xref: g2news1.google.com comp.lang.ada:14008
Date: 2010-09-11T10:07:09+03:00
List-Id: <comp.lang.ada>

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