Re: Inefficient algorithms

[Rick <rickduley@gmail.com>]

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?  How do I use it
in a recursive function?

You help is appreciated.
Thanks