Content deleted Content added
→Requested move 22 October 2019: is B notable? |
→Requested move 22 October 2019: A is not a subset of B |
||
Line 118:
:::This is what I had in mind when I requested this move, except that I thought of leaving a redirect rather than a dab page. I am now convinced that a dab page is better. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 18:10, 25 October 2019 (UTC)
::::I'm not convinced at this point that there's enough sourcing for B or enough to say about it to merit a standalone article. The only source that's been mentioned in reference to meaning B is CLRS, and as far as I can tell it could just be a passing mention. (I don't have a copy of CLRS at hand. Perhaps someone who does would be kind enough to do a reference check?) [[User:Colin M|Colin M]] ([[User talk:Colin M|talk]]) 17:10, 26 October 2019 (UTC)
:::I don't think it's correct to say that A is a subset of B. There are a few ways to think about the "execution" of a non-determinstic algorithm. We can think of it as...
:::# Running on a non-deterministic computer that "magically" makes the right choice at each branching point.
:::# Making ''all'' possible choices at each branching point, along the lines of the [[powerset construction]]
:::# Running on a deterministic computer that exhaustively searches the state space via breadth-first search or some other search algorithm
:::None of these have the property that they "can exhibit different behaviors on different runs for the same input" (unless you deliberately choose a randomized search algorithm for implementation #3 - but this is more like a property of the 'compiler' than the algorithm itself) [[User:Colin M|Colin M]] ([[User talk:Colin M|talk]]) 17:31, 26 October 2019 (UTC)
| |||