Proposals

[btanksley@hifn.com]

From: Lynn H. Maxson [mailto:lmaxson@pacbell.net]
>Jason Marshall wrote:

>What I am describing is what occurs 
>in every AI-based logic engine, an exhaustive 
>true/false testing process.  No more, no less.

I'm still having a hard time figuring out what you mean when you say "an
exhaustive true/false testing process."

However, it's been long known that fully determining a logical equation in
$n$ variables requires $m^n$ steps (with boolean logic m is 2).  For most
practical problems, this is far too time-consuming, and the engines don't
bother.

The traditional meaning of "exhaustive testing" is also vague, but I've seen
it used to mean executing every possible branch path in a program.  As such,
it's always too complicated to be possible.

And the worst thing is that neither of these possibilities helps in any way
with optimization.

>"...they are brute force testing a piece of 
>information only 8 bytes long, against another 
>piece of information only a couple of kilobytes 
>long, looking for the single solution that is the 
>correct one."

>Maybe I just don't understand what problem they are 
>trying to solve

They're trying to find the key for a chunk of encrypted information.
Brute-force search seems the only way, and the problem is "embarassingly
parallel", which means that it's VERY good for parallel processors.

>"Are you familiar with the concepts surrounding the 
>calculation of Order of Complexity of an 
>algorithm?"

>The answer is "maybe, but I'm not sure."  You see I 
>make no claims to holding an "academic" interest in 
>things which may find it "interesting", if not 
>important, to have some measure of the "Order of 
>Complexity" of an algorithm.  I'm not sure I would 
>have had the temerity to ask either my management 
>or the user if they knew it either.  For certain 
>neither gave a damn.  They only wanted it solved.  
>Though I may have done some research to have a 
>better understanding of causes and conditions, they 
>did not care if I used brute force and discovered 
>it by chance in the process as long as I solved it 
>in time.

Wince.  Your customers don't have to understand order of complexity in order
for it to be useful to them, any more than they have to understand
programming languages.  That's your job, not theirs.

I guess it's mine if you don't know it.  Okay, here's my contribution: the
computation you appear to be suggesting is so complex as to be impossible.
Find some other way of getting the result you need.

-Billy