CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

On Sat, 4 Nov 2000, Bill Stewart wrote:

> No - it gives you a direct solution that takes exponential time,
> because there are exponentially many answers the thing could guess,
> each of which takes a polynomial time to validate.
> The "then a miracle occurs" step is that the NTM guesses the
> _correct_ answer - that's why it's hypothetical, rather than real.

There is no guarantee that a NDTM will guess the correct answer at any
stage. The question the NDTM answers over a DTM is "Is there a statistical
algorithm that is more efficient than a deterministic one?".

The answer seems to be "No". It has been shows for example that a NDTM can
address no additional languages over a DTM.

But to address the point I was trying to make,

Since at each step of a NDTM there are k choices in a space of n, k/n.
Assuming the odds of any individual member of the set n being chosen is
1/n.

So, if this probablity space grows faster than P then it must be NP. Even
if the algorithm used to check the result is P itself.

Since the average time to get the correct answer will be k/n there is no
significant efficiency over simply steping through 1 to k which would be
k/n (assuming the resources per n were 1/n).

So, even if you have a P algorithm to test solutions with, there are still
issues like 'solution space' that are not limited by the constraints of
the solution algorithms P-ness.

The problem can be made even more complicated by requiring that no
potential answer is ever checked more than once. This requires a string
matching operation that depending on syntax could be quite complicated,
even NP itself.

So, there are possibly three facets to P-ness:

1.	Solution Algorithm resource use (effects both DTM & NDTM)
2.	Solution space complexity (effects both)
3.	String matching resource use (usualy only NDTM because the
	potential for re-issuing a solution using a RNG is always
	there since the odds are 1/n for each poll of the RNG.)

    ____________________________________________________________________

                     He is able who thinks he is able.

                                           Buddha

       The Armadillo Group       ,::////;::-.          James Choate
       Austin, Tx               /:'///// ``::>/|/      ravage at ssz.com
       www.ssz.com            .',  ||||    `/( e\      512-451-7087
                           -====~~mm-'`-```-mm --'-
    --------------------------------------------------------------------