Content deleted Content added
mNo edit summary |
→For nondeterministic and variable-length protocols: Delete reference to a book that, according to its Google Books reviews, is just a copy-paste of Wikipedia. That obviously makes the reference circular. Someone should probably actually check the proof. <snark>Or would that violate WP:NOR?</snark> Tags: references removed Mobile edit Mobile web edit |
||
Line 40:
Suppose there exists a nondeterministic protocol which solves the problem. Then, by a similar argument to the deterministic example in the previous section, where a deterministic protocol can be obtained from the non-deterministic one by removing all leaf nodes, the deterministic protocol must then also solve the problem.
Since the nondeterministic protocol is finite, it then follows that the protocol represented by the empty tree would solve the problem. Clearly this is not possible. Therefore a nondeterministic protocol which solves the problem cannot exist.
===Proof by symmetry===
| |||