View source for Talk:Yao's principle

{{maths rating|class=stub|priority=low|field=discrete}}
{{WPCS|importance=low|class=stub}}

== Isn't the set of all deterministic algorithms that solve the problem supposed finite? ==

I have lecture slides that suppose it finite, and it seems the proof supposes it as well.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/77.154.204.107|77.154.204.107]] ([[User talk:77.154.204.107#top|talk]]) 11:23, 19 March 2018 (UTC)</small> <!--Autosigned by SineBot-->
:The deterministic algorithms on inputs of a given length are automatically finite (i.e. finiteness is a consequence of the input length, rather than something that needs to be assumed explicitly). But this bound holds on all lengths simultanouesly, and therefore on deterministic algorithms whose input is not a fixed length. The number of such algorithms is not finite. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 16:27, 19 March 2018 (UTC)

== Isn't this only half of Yao's principle? ==
Namely,this page establishes the "easy direction" of Yao's principle, which says that considering arbitrary deterministic algorithms on a chosen distribution of instances is a valid proof technique. (This does not require the minimax theorem to be shown, and is pretty easy). But Yao's principle goes further, also showing that this is also the "right" thing to do (there is no loss in doing so), i.e. this lower bound technique is optimal (the proof of this relies on the minimax theorem, i.e. to show the inequality is an equality). See e.g. Goldreich's comment in http://drops.dagstuhl.de/opus/volltexte/2014/4733/ (Appendix A.1). [[User:Ceacy|Ceacy]] ([[User talk:Ceacy|talk]]) 19:33, 8 April 2018 (UTC)
:Yes, I fully agree that currently the article only presents the most used part of Yao's principle and should be updated. --[[Special:Contributions/2001:62A:4:439:9102:CB78:F991:6972|2001:62A:4:439:9102:CB78:F991:6972]] ([[User talk:2001:62A:4:439:9102:CB78:F991:6972|talk]]) 12:45, 16 April 2018 (UTC)
::Yep yep [[Special:Contributions/119.234.8.12|119.234.8.12]] ([[User talk:119.234.8.12|talk]]) 07:19, 6 July 2023 (UTC)
:::This may be a stab in the dark, but my intuition tells me a key idea in the minimax principle is using [[Game theory]] against the [https://jeffe.cs.illinois.edu/teaching/algorithms/notes/13-adversary.pdf adversary argument], in effect making the adversary play against itself. Of course I’m not sure what the original poster meant as I’m not familiar with that line of work but it’s often the case that the same mathematical principles express themselves in different languages. Happy to collaborate in improving this article if the original poster is interested. [[Special:Contributions/119.234.8.12|119.234.8.12]] ([[User talk:119.234.8.12|talk]]) 08:06, 6 July 2023 (UTC)