Talk:Yao's principle

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

Computer science Low‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Low

This article has been rated as Low-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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. — Preceding unsigned comment added by 77.154.204.107 (talk) 11:23, 19 March 2018 (UTC)[reply]

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. —David Eppstein (talk) 16:27, 19 March 2018 (UTC)[reply]

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). Ceacy (talk) 19:33, 8 April 2018 (UTC)[reply]

Yes, I fully agree that currently the article only presents the most used part of Yao's principle and should be updated. --2001:62A:4:439:9102:CB78:F991:6972 (talk) 12:45, 16 April 2018 (UTC)[reply]

Yep yep 119.234.8.12 (talk) 07:19, 6 July 2023 (UTC)[reply]

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 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. 119.234.8.12 (talk) 08:06, 6 July 2023 (UTC)[reply]