Complexity Theory and Extended Church-Turing Thesis

CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1

Robustness of P The complexity class P is highly robust against modifications to the computational model Multi-tape Turing machines, two-dimensional Turing machines, etc. After studying many examples, one begins to suspect that every realistic model of computation can be simulated by Turing machines with only polynomial slowdown 2

Extended Church-Turing Thesis Let ? be a language Extended Church-Turing Thesis: It is physically possible to build a device that decides ? in polynomial time if and only if ? P. 3

Extended Church-Turing Thesis Extended Church-Turing Thesis: It is physically possible to build a device that decides ? in polynomial time if and only if ? P. If it were true, the thesis would justify using P as our model of tractability However, it seems increasingly likely that the thesis is false! Two key challenges: Randomized Computation and Quantum Computation 4

Randomized computation Sometimes, in our efforts to solve problems and figure things out, we want to make random choices Random sampling for opinion polls Randomized controlled trials in science/medicine What happens if we incorporate this ability into our computational model? 5

Randomized computation To properly study the role of randomness in computing, we ought to define and study a randomized variant of the Turing machine model However, let s temporarily set Turing machines aside we will circle back to them later To build intuition, let s study the role of randomness in a different situation first 6

Communication Complexity Communication Complexity 7

Communication complexity Communication channel Goal: Compute ? ?,? using as little communication as possible In each round, one party sends a single bit while the other party listens At the end, both parties Bob holds ? Alice holds ? announce ? ?,? 8

The equality function We will focus on the case ? = EQ? EQ?: 0,1? 0,1? {0,1} Definition: EQ??,? = 1 if ? = ? if ? ? 0 Does your copy of the database match my copy? 9

Protocols for equality Protocol A: ? + 1 bits of communication 1) Alice sends ? 2) Bob sends EQ??,? Protocol B: 1) For ? = 1 to ?: 2? bits of communication (in the worst case) a) Alice sends ?? b) Bob sends a bit indicating whether ??= ?? 10

Communication complexity of equality Is there a better protocol? Theorem: Every deterministic communication protocol for EQ? uses at least ? + 1 bits of communication in the worst case Before we can prove it, we must clarify how we model communication protocols mathematically 11

Communication protocol model Idea: We model a communication protocol as a binary tree We start at the root node Someone transmits a zero We move to the left child Someone transmits a one We move to the right child (Alice and Bob both know where we are in the tree) 12

Example protocol tree Alice sends ?1 1 0 Bob sends 1 ?1 Bob sends ?1 1 0 1 0 Alice sends ?2 Alice sends ?2 Reject Reject 13

Rigorously defining communication protocols A deterministic communication protocol with ?-bit inputs is a rooted binary tree ? with the following features The vertex set ? is partitioned into three parts: ? = ?? ?? ?? Each vertex ? ?? ?? has two children ( and ?) and is labeled with a function ??:{0,1}? { ,?} Each vertex ? ??has zero children and is labeled accept or reject 14

Rigorously defining communication protocols For ?,? {0,1}?, we define a sequence of vertices ?0,?1, ,?? ?0= the root vertex If ?? ?? (Alice speaks next), then ??+1= ???? If ?? ?? (Bob speaks next), then ??+1= ???? If ?? ?? (the conversation is over), then ? = ? We define leaf ?,? = ?? We define ? ?,? = 1 if leaf ?,? is labeled "accept" 0 if leaf ?,? is labeled "reject" 15

Communication complexity We say that ? computes ? if for every ?,? {0,1}?, we have ? ?,? = ? ?,? The cost of the communication protocol ? is the depth of the tree, i.e., the length of the longest path from the root to the leaf In this model, what happens if Alice and Bob speak at the same time? (Cost = number of rounds = number of bits of communication) A: Trick question. In this model, they never speak simultaneously B: Only one of the messages is successfully transmitted C: Both of the messages are successfully transmitted D: Neither message is successfully transmitted Respond at PollEv.com/whoza or text whoza to 22333 16

?,? ? ,? Rectangle lemma ?,? ? ,? Let ? be any communication protocol with ?-bit inputs Let ?,? ,?,? {0,1}? and let ? be any leaf Rectangle Lemma: If leaf ?,? = leaf ? ,? = ?, then leaf ?,? = leaf ? ,? = ? Proof (sketch): Let ?0,?1, ,?? be the vertices from the root to ? If ?? ??, we must have ???? = ???? = ??+1. Similarly if ?? ?? 17

Communication complexity of equality Theorem: Every deterministic communication protocol that computes EQ? has cost at least ? + 1 Proof: Let ? be any communication protocol that computes EQ? Assume WLOG that every leaf is at the same depth ? Our job is to prove that ? ? + 1 18

?,? ?,? Communication complexity of EQ? ?,? ?,? If ? ?, then leaf ?,? leaf ?,? By the rectangle lemma, it follows that leaf ?,? leaf ?,? Therefore, there are at least 2?distinct leaves labeled accept There is also at least one leaf labeled reject Therefore, there are more than 2? leaves Therefore, 2?> 2?, hence ? ? + 1 19

Communication complexity of EQ? We just proved that computing EQ? requires ? + 1 bits of communication However, there is a loophole! Our impossibility proof only applies to deterministic protocols! 20

Randomized communication complexity Communication channel In a randomized communication protocol, Alice and Bob are permitted to make decisions based on coin tosses Bob holds ? Alice holds ? 21

Randomized communication protocols Mathematically, we model a randomized communication protocol with ?-bit inputs as a deterministic communication protocol with ? + ? -bit inputs for some ? 0 Alice holds ??, where ? 0,1? and ? 0,1? Bob holds ??, where ? 0,1? and ? 0,1? Interpretation: ?,?are the actual inputs, and ?,? are the coin tosses 22