Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity 5 Erample:For the membership problem[11],wherex=[m]and Y=(),and f(x,y)=1 if and only if ry,a naive construction shows a 2-cell proof:with a sorted table storing y,if x Ey,the proof is the cell that contains z,if y,the proof consists of two consecutive cells which are the predecessor and successor of z.The same CPP also works for predecessor search[2]. The notion of cell-probe proofs captures the necessary information to answer queries,and characterizes the nondeterministic probes in the cell-probe model. 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 C 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 [4.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. 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 1 (reduction lemma).For any data structure problem f,if there erists an (s,b,t)-CPP,then there erists 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 (s,bt,1)-CPP. 0 3 Characterization of CPPs We now introduce a combinatorial characterization of CPP.Given a set system Fs2r,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 FP that y∈F Definition 1.We say a set system FC2 is an s x k-partition of y,if F is a union of s number of 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.In this extended abstract,we only provide the characterization of 1-cell proofs.As shown by Lemma 1,this is a canonical case for cell-probe proofs. Theorem 1.There is an(s,b,l)-CPP for f:X×Y→{0，l},if and only if there exists an s x 2b-partition F of Y,such that for every xE X and every y∈Y,there is an F∈F(y)that f(x,F)l=l.Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity 5 Example: For the membership problem[11], where X = [m] and Y = ￾ [m] n
, and f(x, y) = 1 if and only if x ∈ y, a naive construction shows a 2-cell proof: with a sorted table storing y, if x ∈ y, the proof is the cell that contains x, if x 6∈ y, the proof consists of two consecutive cells which are the predecessor and successor of x. The same CPP also works for predecessor search[2]. The notion of cell-probe proofs captures the necessary information to answer queries, and characterizes the nondeterministic probes in the cell-probe model. 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 [4]. 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. 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 1 (reduction lemma). For any data structure problem f, if there exists an (s, b, t)-CPP, then there exists an (s t , bt, 1)-CPP. Proof. Just store every t-tuple of cells in the (s, b, t)-CPP as a new cell in the (s t , bt, 1)-CPP. ut 3 Characterization of CPPs We now introduce a combinatorial characterization of CPP. Given a set system F ⊆ 2 Y , 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 1. We say a set system F ⊆ 2 Y is an s × k-partition of Y , if F is a union of s number of 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. In this extended abstract, we only provide the characterization of 1-cell proofs. As shown by Lemma 1, this is a canonical case for cell-probe proofs. Theorem 1. There is an (s, b, 1)-CPP for f : X × Y → {0, 1}, if and only if there exists an s × 2 b -partition F of Y , such that for every x ∈ X and every y ∈ Y , there is an F ∈ F(y) that |f(x, F)| = 1