Talk:Nondeterministic algorithm

In the intro, "a nondeterministic algorithm is an algorithm with one or more choice points where multiple different continuations are possible". What's a choice point? What's a continuation?

I don't know how to address this comment. If anyone else feels it should be clarified, please do. Rp 16:06, 20 October 2007 (UTC)[reply]

In need of massive work

Wow, there's about 1.2 zillion different types of nondeterministic algorithms (if you include things like stochastic methods, etc). This article is in need of serious attention. Perhaps I'll have to see to that! - 172.133.246.35 06:42, 2 December 2006 (UTC) (JustinWick)[reply]

I think it's better to discuss stochastic methods separately, and link to them here. Rp —Preceding comment was added at 16:02, 20 October 2007 (UTC)[reply]

Is "nondeterministic algorithm" and "probabilistic deterministic algorithm" the same?

In the example "Primality testing" the "Guess an integer..." part of a concrete program/implementation can only use a random number generator to get the job done. Does this mean, that "nondeterministic" and "probabilistic deterministic" are the same in this instance?

It is not the same thing. A probabilistic algorithm is an algorithm in which nondeterminism is resolved by the use of probability. You don't just say that multiple choices are possible, you also give the likelihood for each of the choices to be made. Rp 18:54, 19 October 2007 (UTC)[reply]

I removed another sentence from that example which maintained the suggestion that nondeterminism and random choice are the same. Rp (talk) 20:15, 30 March 2009 (UTC)[reply]

Merge

Can anyone explain why the merge with nondeterminstic programming is a good idea? Or OK if I just remove the merge tags? Sam Staton 16:20, 8 October 2007 (UTC)[reply]

The term "nondeterministic programming" feels like a contradiction to me. We don't usually combine these two words, even though it makes sense to do so. Rp 18:55, 19 October 2007 (UTC)[reply]

I have also read the article. It's too sketchy but it does seem to have merit, as far as I can tell (I am not familiar with the systems mentioned). I think merging it here would be a bad move, because this article is about the idea of a nondeterministic algorithm, which is separate from the idea of actually programming systems in terms of them. Rp 15:59, 20 October 2007 (UTC)[reply]

Reverted edit

I reverted an edit by an anonymous editor. The sentence "A nondeterministic algorithm as an algorithm that, given the same input, may produce different results." is not true: the important thing about a non-deterministic algorithm is that it may make (nondeterministic) choices during execution. Also the first paragraph, even as it stands, is certainly not a "formal definition". If this is unclear, I'm happy to discuss. Sam Staton 10:06, 17 October 2007 (UTC)[reply]

I don't see how the edit being made by an anonymous editor is relevant. That being said, the point of the summery of any article is to make the subject matter approachable.

The 'old summary' is too technical and most definitely not approachable. Considering the old summary to be 99% accurate and completely unapproachable, and considering the new summary to be 80% accurate and totally approachable, I believe the less accurate and approachable definition is the better choice. Wikipedia guidelines also dictate that summaries should be approachable even if they are slightly inaccurate. Users wanting to know more about the subject will continue reading and learn the more correct definition, and people uninterested will leave knowing, for the most part, what they came to learn. If we turn these readers off from reading the article by slapping them across the face with an overly complicated summary, the reader loses and the writer doesn't gain anything.

Your concern about the 'new summary' being inaccurately is unwarranted anyway. Picking apart the word , the inverse of deterministic, yields no importance to making choices. If something is determined then the output has already been decided even before completion. The inverse would be: If something is not determined then the output has not already been decided. There is no implication of choices being made, and if there were and you still think its extremely important, than add that to the simple summary.

I have brought back the simple summary and have fixed a typo in it. I have also renamed the 'formal' definition to 'explicit' definition per your suggestion, which I agree with.

Hello, I think you misunderstood my comment - I don't hold anything against anonymous editors, and I respect your right to anonymity. I just wanted to identify the edit I was talking about.

As I said, it is quite reasonable to ask for a simpler first sentence. But I maintain that your first sentence was far too simple, to the extent that it was wrong. A great many important nondeterminstic algorithms do not return different results for a fixed input. These kinds of algorithms are really important in the study of nondeterminstic polynomial time, in complexity theory. This is one of the main fields of computer science where nondeterminstic algorithms are important. I'm not sure how familiar you are with this.

In line with this, I have tried to correct and improve the opening first sentence. I hope its clearer than the longer paragraph, without being misleading. It's still not perfect, I admit. (In case you find I don't reply to any further discussion: I'll be away now for a few days.) I also changed 'explicit' to 'detailed', since I think that is more appropriate. All the best, Sam Staton 08:42, 18 October 2007 (UTC)[reply]

I do not feel it is appropriate to include the word 'deterministic' in the summary of this article because it goes along the lines of using a a word to describe it self. Again, I stress that explicitly stating that choices are being made isn't necessary. I believe that the word algorithm implies a decision making process is occurring in some fashion.

I don't know whether I understand your objection, and I have no idea how to address it. Can you please suggest a rewording that would be more to your taste? (And sign your comments by appending four tildes.) Thanks. Rp 15:52, 21 October 2007 (UTC)[reply]