CDR: Re: Minesweeper and defeating modern encryption technology
ravage at EINSTEIN.ssz.com
Sun Nov 5 12:06:45 PST 2000
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
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.
The Armadillo Group ,::////;::-. James Choate
Austin, Tx /:'///// ``::>/|/ ravage at ssz.com
www.ssz.com .', |||| `/( e\ 512-451-7087
More information about the cypherpunks-legacy