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@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------