Talk:Nondeterministic algorithm: Difference between revisions

Revision as of 03:36, 31 October 2019

Revision as of 04:53, 8 November 2019

Line 109:

{{requested move/dated|Nondeterministic computation}}

[[:Nondeterministic algorithm]] → {{no redirect|Nondeterministic computation}} – The present title is clearly ambiguous as shown in the preceding thread of this talk page, and the disambiguation hatnote that I have added to the article. The proposed title is much clearer as referring to effective computation (the subject of the article rather than to abstract algorithms. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 17:36, 22 October 2019 (UTC) <small>--'''''Relisting.'''''&nbsp;[[User:Steel1943|<span style="color: #2F4F4F;">'''''Steel1943'''''</span>]] ([[User talk:Steel1943|talk]]) 03:35, 31 October 2019 (UTC)</small> <small>—'''''Relisting.'''''&nbsp;[[User:Wugapodes|Wug·]][[User talk:Wugapodes|a·po·des]]​ 04:53, 8 November 2019 (UTC)</small>

*'''Oppose''' This article is, in its current state, confusing, but the proposed rename won't resolve the confusion. It seems there are at least two kinds of things that are referred to as "Nondeterministic algorithms" in the literature: A) Algorithms written using primitives associated with [[nondeterministic model of computation|nondeterministic models of computation]]/NTMs. This is discussed above by Sam Staton, RobinK, and Ph14nix above, and in [https://cs.nyu.edu/courses/spring03/G22.2560-001/nondet.html this EL] (and the NIST EL and the Floyd paper) B) Algorithms whose behaviour might vary from run to run. According to Schapel above, [[CLRS]] uses this sense (though they don't indicate whether the work specifically uses the phrase "nondeterministic algorithm"). This other meaning is also alluded to in some other comments above, including a reply from Robink. Right now, this article gives a mish-mash of concepts A and B, which is bad, because they're totally different.