Yao's min-max theorem: how can the set of deterministic algorithms be finite?

Question

I'm read Randomized Algorithms book by Motwani, the part about Yao's min-max technique:

Consider a problem where the number of distinct inputs of a fixed size is finite, as is the number of distinct (deterministic, terminating, and always correct) algorithms for solving that problem.

Let $\Pi$ be a problem with a finite set $\mathcal{I}$ of input instances(of a fixed size), and a finite set of deterministic algorithms $\mathcal{A}$, then

Proposition 2ドル.5$ (Yao's Minimax Principle): For all distributions p over $\mathcal{I}$ and $\boldsymbol{q}$ over $\mathcal{A}$, $$ \min _{A \in \mathcal{A}} \mathbf{E}\left[C\left(I_{p}, A\right)\right] \leq \max _{l \in \mathcal{I}} \mathbf{E}\left[C\left(I, A_{q}\right)\right] $$ In other words, the expected running time of the optimal deterministic algorithm for an arbitrarily chosen input distribution $\boldsymbol{p}$ is a lower bound on the expected running time of the optimal (Las Vegas) randomized algorithm.

It's reasonable that the number of distinct inputs of fixed size is finite, say the number of graphs with 100ドル$ vertices is finite. But how come the number of distinct deterministic algorithms is also finite? That is to say, the number of determinist algorithms to find the min-cut for graph of 100ドル$ vertices is finite. I'm confused here:

• What exactly does it mean here by being finite?
• Why these two sets has to be finite?

• Steven: I don't think that the set of algorithms is required to be finite. In fact, if the problem admits at least one algorithm then the set of algorithms is not finite (you can get an infinite number of algorithms by simply doing irrelevant steps before returning). Notice however that if we restrict to problems that admit at least one algorithm, the statement as written is technically still (vacuously) true since it holds for all problems that satisfy the required conditions (i.e., none).
• Mengfan Ma: @Steven That's exactly what I'm think about. But the author even "reiterate that these observations apply only to scenarios where the number of algorithms is finite."
• Steven: The second sentence that you added is not saying that the set of all possible algorithms that solve $\Pi$ must be finite but rather it is telling you to choose a finite set of algorithms that solve $\Pi$. Read it as: Let $\Pi$ be a problem, fix an input size and let $\mathcal{I}$ be the set of all instances of $\Pi$ of that size. Let $A$ be a finite set of algorithms (that solve $\Pi),ドル then: [...]
• Mengfan Ma: But if we just choose a finite set of algorithms, can we get the lower bound for all randomized algorithms? or we just obtain lower bound for randomized algorithms based on the algortihms we choose?
• Steven: You only get a lower bound for randomized algorithms whose deterministic instantiations match the algorithms in $A$. If the maximum number of random choices of your randomized algorithm is bounded by a function of the input size $n$ then you can indeed choose a finite set $A$ corresponding to all possible deterministic instantiations (by fixing the observed random bits). However I don't think that Yao's Principle actually requires $A$ to be finite.

Answer 1

The set of all algorithms isn't finite. Motwani isn't claiming that the set of all algorithms is finite.

Rather, Motwani is proposing we examine a situation where we have some finite set of algorithms. In other words, suppose we have a set $\mathcal{A}$ of algorithms. If $\mathcal{A}$ is finite, then Motwani says there are some facts we can prove, and the exposition explains some of those facts.

Nowhere does Motwani claim or assume that $\mathcal{A}$ is the set of all algorithms. You can consider any set of algorithms you want. If your set is finite, then the facts shown there will hold. If your set is infinite, they might not.

---

To put it another way, "Consider a problem where X" is not a claim that X holds; it is a statement that if X holds, then some other things will follow.

• Mengfan Ma: I see. So does the Yao' theorem still hold if $\mathcal{A}$ is the set of all algorithms?
• D.W.: @MengfanMa, I don't know enough to answer off the top of my head. I suggest you look at the proof of the proposition carefully to see if it can be adapted to the infinite case; research this question; and if neither answers your question, post a new question separately to ask about that.
• Mengfan Ma: I've checked Yao's original paper, $\mathcal{A}$ is defined as "the family of pure algorithms that make no redundant tests".