Talk:Yao's principle

  1. Home
  2. Wiki

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)[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?

[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)[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]

Comments on clarity

[edit]
  • I think the lead is a bit hard to follow. I would prefer like a setup for both points. Instead of The optimal performance that can be obtained by a deterministic algorithm something like "Given any deterministic algorithm ...".
  • cost measure this should be defined what is a valid "cost measure" is that different from a Measure (mathematics)?

Czarking0 (talk) 17:57, 26 April 2025 (UTC)[reply]

(1) It is extremely important to use quantifiers precisely in this topic, especially because the two nested quantifiers on algorithms and inputs are reversed going between the random and non-random sides of the equality. You are starting off on a bad foot by attempting to use "any" as a quantifier. It is ambiguous, sometimes meaning "for all", sometimes meaning "make an arbitrary choice", etc. In this case, we are talking about lower bounds that apply to all algorithms, not algorithm-specific bounds that apply to a single given algorithm.
(2) Yes. It is unrelated to mathematical measure theory; it is just the colloquial sense of the English word "measure", not a technical word. See also complexity measure. Also, the lead is not the place for detailed definitions of notions like complexity measures; doing so tends to make things more technical when what is needed is a broad overview. The later article text that this summarizes makes clear that it can actually be an arbitrary function that maps (algorithm,input) pairs to numbers, and the applications section provides many specific examples of such functions. —David Eppstein (talk) 18:25, 26 April 2025 (UTC)[reply]
Thanks, I'll continue to give some more of these.
  • when a specific input distribution has been shown to be hard Is this referring to a big O greater than polynomial time? Should hard be blue? If not what does hard mean here
Czarking0 (talk) 06:34, 1 May 2025 (UTC)[reply]
Then Consider an arbitrary cost measure of an algorithm on an input should really be "Consider an arbitrary cost measure which always has finite costs" right? Czarking0 (talk) 06:48, 1 May 2025 (UTC)[reply]
If I say "consider an integer which always is finite" am I really saying anything more informative than "consider an integer"? The way cost measures are defined later it is impossible for them to be infinite, so it would be redundant to constrain them to forbid the (nonexistent) infinite ones.
As for "shown to be hard": first of all, big O is the wrong thing to be thinking about for lower bounds, which when they involve O-notation at all involve big Omega. Second, we do not need to hide constant factors in O-notation to use this principle; it works regardless, and trying to carry around the additional levels of nested quantification involved in mixing big-O notation with this lemma is probably more complication than it is worth. Third, the resource in question is not necessarily time, and being polynomial is not the only way to distinguish easy from hard. Fourth, this wording is deliberately informal, really meaning only something like causing the algorithm to take more of some resource than some other distribution. It is just the colloquial English meaning of the word, synonymous with "difficult". It does not require a link. This and many other expository works follow a style where a notion is presented first in an informal style to make the intuition clear, and then formalized later. Trying to get an exact pedantic and formal definition right from the start is a different style, and one that is much more WP:TECHNICAL, something we are trying to avoid. This article also presents very precise technical statements, after the informal intuition. It is important not to mix those two things up. —David Eppstein (talk) 06:57, 1 May 2025 (UTC)[reply]
If I Ctrl+F for "cost measure" or "cost" I don't see the more precise definition you are referring to can you please point it out? I sort of disagree that it is fair to say that this use of hard is colloquial. In colloquial English one does not show things to be hard. Would it be more clear to say "when a specific input distribution has been shown to have a lower bound on the cost for deterministic algorithms"? In terms of articel structure I think the Formulation title is throwing me off as the title makes me expect something more formal. I hear what you are saying about starting the article with a more intuitive vibe and upping the details as you get further into the article. Maybe "Core principal" or "Basics" are a better title for the section? Also grouping all the variable definitions for the Formulation section to a list format at the top might make the paragraphs in the section a cleaner read. Czarking0 (talk) 14:51, 1 May 2025 (UTC)[reply]
It's the first line of "Formulation": Consider an arbitrary cost measure of an algorithm on an input . The word "arbitrary" means what it says: it is an arbitrary (real valued) function of A and x. That is the definition. Any real function. The meaning you assign to this function comes from whatever application you have for the lemma but is not baked into its definition. As for grouping all the variables into a list: they are already grouped into that one first paragraph, and see WP:USEPROSE. —David Eppstein (talk) 16:51, 1 May 2025 (UTC)[reply]
I am not suggesting to group the variables because I am unfamiliar with USEPROSE I am suggesting to group the variable definitions because the prose is not easy to follow. The prose would read better if you didn't constantly interrupt it with variable definitions. Czarking0 (talk) 20:06, 1 May 2025 (UTC)[reply]
Thanks for the clarifications! I made a couple ce for what I think is more clarity. Also I noticed you editted out most of the uses of any which I think is a good idea. I see you left this one For these problems, for any fixed number of elements is that intentional? I also think the double use of for does not sound good but I am not confident in rewording this to your standard. Czarking0 (talk) 20:16, 1 May 2025 (UTC)[reply]
It's ok in that context because "fixed" fixes the ambiguity. Also, quantifiers quantifiers quantifiers. I keep having to tell you, pay attention to the quantifiers. There are two uses of the word "for" here because there are two quantifiers. —David Eppstein (talk) 22:24, 1 May 2025 (UTC)[reply]
When myself or anyone else is not understanding your point after making it several times repeating the same word over an over again is probably the least effective way to communicate. You said quantifiers 5 times in that comment. Let's clarify what that means. I am not really sure what you mean by "keep having to tell you" are you referring to my comments about the green text above? If this is what you are talking about then I assume the quantifiers in the green text are "For these" and "for any"? I am not saying that the two uses of for are incorrect but the prose sounds bad. I would like "For these problems, and any fixed number of elements" works as well but sounds better. Czarking0 (talk) 14:52, 2 May 2025 (UTC)[reply]
Ok, let me say it another way. If you do not clearly understand the mathematics please stop trying to edit the article to reflect your non-understanding. Your edits are not an improvement. I was hoping to convey that the thing that seems to be least understood in your edits is the way that English word order translates into mathematical quantifiers, but the broader point is that vagueness in your understanding will not lead to good edits. Your talk page comments here, pointing out the parts where you are having trouble understanding, are more useful. —David Eppstein (talk) 17:03, 2 May 2025 (UTC)[reply]
You haven't said it in another way. I specifically asked what you mean by quantifiers and gave examples of what I understood you to mean.
I am not "trying to edit the article to reflect your non-understanding". I am trying to improve the article. Czarking0 (talk) 18:07, 2 May 2025 (UTC)[reply]