[35] Define the protocol-independent communication complexity TCC(x, y|C(P) ≤ i), of computing a function f(x, y), as the minimum CC(x, y|P) over all deterministic total protocols P computing f(x, y) for all pairs (x, y) (l(x) = l(y) = n) with C(P) ≤ i. For example, TCC(x, y|C(P) ≤ n + O(1)) = 0 for all computable functions f and all x, y.

(a) Show that for every computable function f(x, y) its TCC(x, y|C(P) ≤

i) is always at most the TCC(x, y|C(P) ≤ i) of the identity function I(x, y)=(x, y), for every x, y, i.

(b) Show that for every computable function f we have TCC(x, y|C(P) ≤
i) ≥ C(f(x, y)|x) − i − O(log i). For f = I this gives TCC(x, y|C(P) ≤
i) ≥ C(y|x) − i − O(log i).

(c) Show that for the identity function I, restricting the protocols to one-way (Bob sends a single message to Alice only) does not significantly alter the protocol-independent communication complexity for total protocols: TCC(x, y|C(P) ≤ i+O(1), P is one-way) ≤ TCC(x, y|C(P) ≤ i), where in the right-hand side P is allowed to be two-way.
Comments. Source: [H.M. Buhrman, H. Klauck, N.K. Vereshchagin, and P.M. B. Vit´anyi, Ibid.].