[33] Let the protocol-independent communication complexity PCC(x, y|C(P) ≤ i) stand for the minimum CCP (x, y) over all partial deterministic protocols P of complexity at most i computing f correctly on input (x, y) (on other inputs P may output incorrect results or not halt). Trivially, PCC(x, y|C(P) ≤ i) ≤ TCC(x, y|C(P) ≤ i) for every computable function.

(a) Show that for the identity function I we have C(y|x)−i−O(log i) ≤

PCC(x, y|C(P) ≤ i) ≤ PCC(x, y|C(P) ≤ i, P is one-way) ≤ C(y) for all x, y, i such that i is at least log C(y) + O(1). The addition ‘one-way’

means that Bob communicates with Alice but not vice versa.

(b) Prove that for the identity function I we have PCC(x, y|C(P) =

O(log n), P is one-way) ≤ C(y|x) + O(log n), for all x, y of length n.

Comments. Item

(a) is obvious. Comparing Item

(b) with Exercise 6.11.4, Item (c), we see that protocol-independent communication complexity for the identity function I of one-way partial deterministic protocols is strictly less than that of one-way total deterministic protocols (there are no noncommunicable objects for protocol-independent communication complexity of partial protocols). Moreover, by Exercise 6.11.3, Item

(c), the protocol-independent communication complexity for the identity function I of one-way total deterministic protocols equals that of twoway ones. Hint for Item (b): use Muchnik’s theorem, Theorem 8.3.7, on page 676. Source: [H.M. Buhrman, H. Klauck, N.K. Vereshchagin, and P.M.B. Vit´anyi, Ibid.].