Jump to content

Talk:Yao's principle

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 19:42, 11 November 2024 (definitely not stub; C or B?). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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]