Lecture 12.A glimpse of computational complexity This year's offering of the complexity course focuses on concrete models,and we'll use this last lecture to say something about various models defined by Turing machines.The standard (and recent)references are textbooks by Arora and Barak [AB09]and Goldreich [Gol08].For automata and Turing machines,a good textbook is [Sip]. Due to the vast amount of the materials,we cannot provide proof for most theorems,though we'll sketch some key ideas of the proof. 1.Time and space TIME(t(n)):Languages that can be decided in time t(n)on a deterministic Turing machine. Theorem (Hierarchy):TIME(t(n))TIME(@(t(n)log t(n))) (Proof idea:Diagonalization.) P=UTIME(n):Languages that can be decided in polynomial time on a deterministic Turing machine. Examples:Matching,MaxFlow,LP,PRIMES,.. EXP=U=TIME(2):Languages that can be decided in exponential time on a deterministic Turing machine. SPACE(s(n)):Languages that can be decided in space s(n)on a deterministic Turing machine PSPACE =U=SPACE(n):Languages that can be decided in polynomial space on a deterministic Turing machine. Theorem.TQBF is PSPACE-complete,where TQBF ={x:QiyQ2y2...Qkyk,(x,y1...,y)=1}for some E P,constant k,and quantifiers QiE(3,and y1,...,yk of polynomial lengths.Lecture 12. A glimpse of computational complexity This year’s offering of the complexity course focuses on concrete models, and we’ll use this last lecture to say something about various models defined by Turing machines. The standard (and recent) references are textbooks by Arora and Barak [AB09] and Goldreich [Gol08]. For automata and Turing machines, a good textbook is [Sip]. Due to the vast amount of the materials, we cannot provide proof for most theorems, though we’ll sketch some key ideas of the proof. 1. Time and space 𝐓𝐈𝐌𝐄(𝑡(𝑛)): Languages that can be decided in time 𝑡(𝑛) on a deterministic Turing machine. Theorem (Hierarchy): 𝐓𝐈𝐌𝐄(𝑡(𝑛)) ≠ 𝐓𝐈𝐌𝐄(𝜔(𝑡(𝑛) log 𝑡(𝑛))). (Proof idea: Diagonalization.) 𝐏 = ⋃ 𝐓𝐈𝐌𝐄(𝑛 𝑐 ) 𝑐≥1 : Languages that can be decided in polynomial time on a deterministic Turing machine. ⚫ Examples: Matching, MaxFlow, LP, PRIMES, … 𝐄𝐗𝐏 = ⋃ 𝐓𝐈𝐌𝐄(2 𝑛 𝐶 ) 𝑐≥1 : Languages that can be decided in exponential time on a deterministic Turing machine. 𝐒𝐏𝐀𝐂𝐄(𝑠(𝑛)): Languages that can be decided in space 𝑠(𝑛) on a deterministic Turing machine 𝐏𝐒𝐏𝐀𝐂𝐄 = ⋃ 𝐒𝐏𝐀𝐂𝐄(𝑛 𝑐 ) 𝑐≥1 : Languages that can be decided in polynomial space on a deterministic Turing machine. Theorem. TQBF is PSPACE-complete, where 𝑇𝑄𝐵𝐹 = {𝑥: 𝑄𝑖𝑦1𝑄2𝑦2 …𝑄𝑘 𝑦𝑘 ,𝜙(𝑥, 𝑦1 , . . , 𝑦𝑘 ) = 1} for some 𝜙 ∈ 𝐏, constant k, and quantifiers 𝑄𝑖 ∈ {∃, ∀} and 𝑦1 , …, 𝑦𝑘 of polynomial lengths