1:6·Y.Yin The fact that this simple example also works for predecessor has an impor- tant implication.Combining with the super-constant lower bound for predeces- sor search [Patrascu and Thorup 2006],this gives an example where one can separate deterministic and nondeterministic complexity. We remark that cell-probe proofs characterize the nondeterministic probes in the cell-probe model.Specifically,the verifier o is just a nondeterministic cell-probing algorithm.It is natural to see that for a cell-probe scheme,for any query,the cells probed by an adaptive algorithm contain a cell-probe proof. This can be seen as a data structure counterpart of P NP. It is important to note that although a data structure problem is nothing but a boolean function,CPP is very different from the certificate complexity of boolean functions [Buhrman and de Wolf 2002].In CPP,the prover and the verifier communicate with each other via a table structure,which distinguishes CPP from standard certificate complexity.For any data structure problem,the table structure can always store the results for all queries,making one cell- probe sufficient to prove the result,which is generally impossible in the model of certificate complexity. We should also be specific that the model of cell-probe proofs prohibits ran- domization.The nondeterministic model for randomized data structures is a possible future direction. Unlike adaptive cell-probes,CPP has a static nature,which is convenient for reductions.As stated by the following lemma,any CPP can be trivially reduced to 1-cell proofs. LEMMA 2.1 REDUCTION LEMMA.For any data structure problem f,if there exists an (s,b,t)-CPP,then there exists an (st,bt,1)-CPP. PROOF.Just store every t-tuple of cells in the(s,b,t)-CPP as a new cell in the (sf,bt,1)-CPP. ▣ 3.CHARACTERIZATION OF CPPS We now introduce a combinatorial characterization of CPP.Given a set system FC2Y,for any yY,we let F(y)=(FEFIy e F).For convenience,for a partition P of y,we abuse this notation and let P(y)denote the set FeP that y∈F. Definition 3.1.We say a set system FC2Y is an s x k-partition of y if F is a union ofs many partitions of y,where the cardinality of each partition is at most k. This particular notion of partitions of y fully captures the structure of cell- probe proofs.The following theorem provides a full characterization of cell- probe proofs. THEOREM3.2.There is an(s,b,t)-CPP for f:X×Y→{0,1}，if and only if there exists an s x 26-partition F of Y,such that for every x e X and every yeY,there exist F1,...,FeF(y)such that f(x,F)=1. PROOF.First,we prove the“only if”part. ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.1: 6 · Y. Yin The fact that this simple example also works for predecessor has an impor￾tant implication. Combining with the super-constant lower bound for predeces￾sor search [Patras ˘ ¸cu and Thorup 2006], this gives an example where one can separate deterministic and nondeterministic complexity. We remark that cell-probe proofs characterize the nondeterministic probes in the cell-probe model. Specifically, the verifier v is just a nondeterministic cell-probing algorithm. It is natural to see that for a cell-probe scheme, for any query, the cells probed by an adaptive algorithm contain a cell-probe proof. This can be seen as a data structure counterpart of P ⊆ NP. It is important to note that although a data structure problem is nothing but a boolean function, CPP is very different from the certificate complexity of boolean functions [Buhrman and de Wolf 2002]. In CPP, the prover and the verifier communicate with each other via a table structure, which distinguishes CPP from standard certificate complexity. For any data structure problem, the table structure can always store the results for all queries, making one cell￾probe sufficient to prove the result, which is generally impossible in the model of certificate complexity. We should also be specific that the model of cell-probe proofs prohibits ran￾domization. The nondeterministic model for randomized data structures is a possible future direction. Unlike adaptive cell-probes, CPP has a static nature, which is convenient for reductions. As stated by the following lemma, any CPP can be trivially reduced to 1-cell proofs. LEMMA 2.1 REDUCTION LEMMA. For any data structure problem f, if there exists an (s, b,t)-CPP, then there exists an (st , b t, 1)-CPP. PROOF. Just store every t-tuple of cells in the (s, b,t)-CPP as a new cell in the (st , b t, 1)-CPP. 3. CHARACTERIZATION OF CPPS We now introduce a combinatorial characterization of CPP. Given a set system F ⊆ 2Y , for any y ∈ Y, we let F(y) = {F ∈ F | y ∈ F}. For convenience, for a partition P of Y, we abuse this notation and let P(y) denote the set F ∈ P that y ∈ F. Definition 3.1. We say a set system F ⊆ 2Y is an s × k-partition of Y if F is a union of s many partitions of Y, where the cardinality of each partition is at most k. This particular notion of partitions of Y fully captures the structure of cell￾probe proofs. The following theorem provides a full characterization of cell￾probe proofs. THEOREM 3.2. There is an (s, b,t)-CPP for f : X × Y → {0, 1}, if and only if there exists an s × 2b -partition F of Y, such that for every x ∈ X and every y ∈ Y, there exist F1,..., Ft ∈ F(y) such that f(x,∩t i=1Fi) = 1. PROOF. First, we prove the “only if ” part. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010