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=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD,
	FREEMAIL_FROM autolearn=no 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
Path: 
 g2news1.google.com!postnews.google.com!s24g2000pri.googlegroups.com!not-for-mail
From: Rick <rickduley@gmail.com>
Newsgroups: comp.lang.ada
Subject: Re: Inefficient algorithms
Date: Sat, 11 Sep 2010 02:07:24 -0700 (PDT)
Organization: http://groups.google.com
Message-ID: 
 <0ce6d303-c8ff-4688-8372-00238f52d1d4@s24g2000pri.googlegroups.com>
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
 <8f0nd6F8ucU1@mid.individual.net> <8f0o4uFct8U1@mid.individual.net>
NNTP-Posting-Host: 114.75.15.132
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1284196044 32238 127.0.0.1 (11 Sep 2010 09:07:24
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sat, 11 Sep 2010 09:07:24 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: s24g2000pri.googlegroups.com; posting-host=114.75.15.132;
 posting-account=q18aiAoAAADbiIPIlD5R8oYVGhuoBvVA
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1;
 Trident/4.0; GTB6.5; .NET CLR 2.0.50727; .NET CLR 3.0.4506.2152;
 .NET CLR 3.5.30729),gzip(gfe)
Xref: g2news1.google.com comp.lang.ada:14010
Date: 2010-09-11T02:07:24-07:00
List-Id: <comp.lang.ada>

On Sep 11, 3:07=A0pm, 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. =A0All I can find is 'C' code I can't decipher. =A0Can someon=
e
> >> 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
> =A0 =A0 =A0 =A0. =A0 =A0 =A0@ =A0 =A0 =A0 .

I must be a bit daft, Niklas, but I don't get it.
What sort of a Boolean formula are you talking about?  How do I use it
in a recursive function?

You help is appreciated.
Thanks