Introduction to Complexity Theory Spring 2025

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

Arithmetic formulas Definition: A ?-variate arithmetic formula is a rooted binary tree Each internal node is labeled with + or Each leaf is labeled with 0, 1, 1, or a variable among ?1, ,?? + + ?1 ?1 ?2 ?2 1 2

Polynomial identity testing Problem: Given an arithmetic formula ?, determine whether ? 0 As a language:PIT = ? ? is an arithmetic formula and ? 0 Open Question: Is PIT P? Next 10 slides: We will prove PIT BPP 3

Evaluating an arithmetic formula Let ? be a ?-variate arithmetic formula and let ? ? Lemma: Given ?, ? , one can compute ? ? in polynomial time. 12 ?1= 2 6 2 ?2= 4 + + 4 ? ?1,?2 = 12 ?2 ?1 ?1 2 4 2 Possible concern: How big can these numbers get? ?2 1 4 4

Bound on the magnitude of the output Let ? = max ?1, ?2, , ??,2 and let ? be the number of leaves ??. Proof by induction: Claim: ? ? Base case: ? = 1: trivial ??? ???= ?? If ? ? = ?? ? ?? ? , then ? ? = ?? ? ?? ? ???+ ??? ?? If ? ? = ?? ? + ?? ? , then ? ? ?? ? + ?? ? 5

Evaluating an arithmetic formula Let ? be a ?-variate arithmetic formula and let ? ? Lemma: Given ?, ? , one can compute ? ? in polynomial time. Proof sketch: Evaluate the nodes one by one, starting at the leaves ? 2? and ? ?, so each node outputs ? such that ? ?? 2?2 In other words, ? is an ? ?2-bit integer There are ? ? nodes, and we can do arithmetic in polynomial time 6

Note on standards of rigor Going forward, when we analyze specific algorithms, we will often assert that they run in polynomial time without a rigorous proof In each case, one can rigorously prove the time bound by describing a TM implementation and reasoning about the motions of the heads But this is tedious Note: We still prove correctness whenever it is nontrivial, just not efficiency You should follow this convention on exercise 14 and beyond 7

Polynomial identity testing We are given ? , where ? is an arithmetic formula Goal: Figure out whether ? 0 If ? 0, then ? ? = 0 for all ? Even if ? 0, there still might be some ? such that ? ? = 0 How often can this occur? 8

How many roots can a nonzero degree-? two-variable polynomial have? Counting roots B: Up to ?2 A: Up to ? D: Only finitely many, but there is no bound in terms of ? C: It might have infinitely many Respond at PollEv.com/whoza or text whoza to 22333 Fundamental Theorem of Algebra Every nonzero degree-? univariate polynomial has at most ? real roots What about a multivariate polynomial? 9

Polynomial Identity Lemma Even if ? 0, it might have infinitely many roots ? = ? ?2 Intuition: Roots are nevertheless rare Let ? ? be a multivariate polynomial of degree at most ? in each variable individually Let ? and assume ? is finite Polynomial Identity Lemma: If ? 0, then ? 10 ?? ?? ?? 1 10

Polynomial Identity Lemma: If ? 0, then ?10 ?? ?? ??1 ? ??? ?? and suppose ? 0 Proof when ? = 2: Write ? ?,? = ?=0 ? 10 ?2= ? ? ? ?,? = 0 ? ? = ? ? ? ?,? = 0 + ? ? ? ?,? = 0 ? ? =0 ? ? + ? ? ? ? 0 Fundamental Theorem of Algebra = 2? ? 11

Theorem: PIT BPP Given ? with ? variables and ? leaves: 1. Let ? = 1, ,3?? Polynomial time 2. Pick ? ?? uniformly at random 3. Compute ? ? Correctness proof: 4. If ? ? = 0, accept, otherwise reject Degree ? (prove by induction) If ? 0, then Pr accept = 1 If ? 0, then by the Polynomial Identity Lemma, we have ? 10 ?? ?? ?? ?? 1 ?? 3??=1 Pr accept = Pr ? ? = 0 = = ?? 3 12

Polynomial identity testing: Recap It is an open question whether PIT P We proved PIT BPP Does that mean we should consider PIT tractable? 13

The complexity class BPP Definition:BPP is the set of languages ? 0,1 such that there exists a randomized polynomial-time Turing machine that decides ? with error probability 1/3 14

Amplification lemma Suppose a language ? 0,1 can be decided by a time-? Turing machine ?0 with error probability 1/3 Let ? be any constant Amplification Lemma: There exists a randomized time-? Turing machine that decides ? with error probability 3 ??, where ? ? = ? ? ? ??. As ? , the error probability goes to 0 extremely rapidly! 15

If ?0 uses ?(?) many random bits, then how many random bits does the new TM use? Proof of the amplification lemma (1 slide) A:? ? + ?? B:?(?) ?? For simplicity, assume that for every ? ?, we have Pr ?0 accepts ? = 1 C:? ?? D: Not enough information For ? ?, we merely assume Pr ?0 accepts ? 1/3 Respond at PollEv.com/whoza or text whoza to 22333 Given ? 0,1?: For ? = 1 to ??: 1) Time complexity: ? ? ? ?? Simulate ?0 on ? using fresh random bits. If it rejects, reject. a) 2) Accept. If ? ?, then Pr ? accepts ? = 1 If ? ?, then Pr ? accepts ? 1/3??= 1/3?? 16

BPP as a model of tractability Because of the amplification lemma, languages in BPP should be considered tractable A mistake that occurs with probability 1/3100 can be safely ignored (Even if you use a deterministic algorithm, can you really be 100% certain that the computation was carried out correctly?) 17

Extended Church-Turing Thesis Extended Church-Turing Thesis: For every ? 0,1 , it is physically possible to build a device that decides ? in polynomial time if and only if ? P. Is PIT a counterexample? 18