EECS 376 Lecture Notes - Lecture 3: Increment And Decrement Operators, Turing Reduction
20 Jun 2016
School
Course
Professor
Document Summary
Consider the function gt : {0, 1}n {0, 1}n {0, 1} de ned by. 0 if x y otherwise where x, y {0, 1}n are interpreted as binary numbers. Recall that the function eq : {0, 1}n {0, 1}n {0, 1} is de ned by. In lecture, we showed that d(eq) = n. now observe that x = y x y and y x, so. Eq(x, y) = 1 gt(x, y) = 1 and gt(y, x), Therefore, we can compute eq(x, y) by computing gt(x, y) and gt(y, x), and then having one player send their result to the other. Therefore, any protocol p that computes gt can be used to make a protocol p that computes eq and which satis es d(p ) = 2 d(p) + 1. Since we know that any such protocol p satis es d(p ) n, it follows that d(p) (n 1)/2.
