Talk:Yao's principle: Difference between revisions
m Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "Stub" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{Maths rating}}, {{WPCS}}. Remove 1 deprecated parameter: field. Tag: |
try GA nom |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{GA nominee|07:26, 4 December 2024 (UTC)|nominator=—[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]])|page=1|subtopic=Computing and engineering|status=|note=|shortdesc=Equivalence of average-case and expected complexity}} |
|||
{{WikiProject banner shell|class= |
{{WikiProject banner shell|class=| |
||
{{WikiProject Mathematics|priority=low}} |
{{WikiProject Mathematics|priority=low}} |
||
{{WikiProject Computer science|importance=low}} |
{{WikiProject Computer science|importance=low}} |
||
Latest revision as of 07:27, 4 December 2024
 | Yao's principle is currently a Computing and engineering good article nominee. Nominated by —David Eppstein (talk) at 07:26, 4 December 2024 (UTC) Any editor who has not nominated or contributed significantly to this article may review it according to the good article criteria to decide whether or not to list it as a good article. To start the review process, click start review and save the page. (See here for the good article instructions.) Short description: Equivalence of average-case and expected complexity |
 | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
Isn't the set of all deterministic algorithms that solve the problem supposed finite?
[edit]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)
- 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)
Isn't this only half of Yao's principle?
[edit]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)
- 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)
- Yep yep 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 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)
- Yep yep 119.234.8.12 (talk) 07:19, 6 July 2023 (UTC)