Clarification of Homework 2. We say that an algorithm B has the "support property" if, at any step, the configuration of B (i.e., B's cache) is in the support of the work function. Problem: Prove that, for any proof of competitiveness for the paging problem for k = 2, the optimal cache is in Supp(w) without loss of generality. Here is what you need to prove. Suppose that A is any randomized online algorithm for the paging problem for k = 2. (Since every deterministic algorithm is trivially a randomized algorithm, this covers that, too.) Suppose that there exists a numbers C >= 1 and K_1 such that, for any randomized algorithm B_1 which has the support property, and for any request sequence rho, Ecost_A(rho) <= K_1 + C Ecost_B_1(rho). (E denotes expected value.) Then, there exists a constant K_2 such that, for any algorithm B_2, and any request sequence rho, Ecost_A(rho) <= K_2 + C Ecost_B_2(rho). It is extremely important to get the quantifiers right, so I will write it formally. Let RAlg be the set of all randomized algorithms for the problem, including offline and online algorithms. Let RAlgSP be the set of all randomized algorithms for the problem which have the support property. Let RS be the set of all possible request sequences. Let F be the boolean function defined (using Pascal notation) as follows: function F(A,B:RAlg; rho:RS; C,K:real):boolean; begin F := Ecost_A(rho) <= K + C*Ecost_B(rho) end; The statement that we need to prove is then formally written below. (forany A in RAlg)(forany C in reals) ( (forsome K in reals)(forany B in RAlgSP)(forany rho in RS)F(A,B,rho,C,K) implies (forsome K in reals)(forany B in RAlg)(forany rho in RS)F(A,B,rho,C,K) ) Some people have trouble understanding any statement where the quantifiers are nested two deep. How deeply are the quantifiers nested in the statement above? It depends how far back into the definitions you look. At first glance, there appear to be five nesting levels of quantifiers. But that increases if you count the fact that the definition of the the support property involves quantifiers.