Complexity Structural complexity: High-level questions. -P vs.NP.P vs.BPP.P vs.PSPACE.etc. -Many conditional results. ·Concrete complexity Low-level questions. Lower bounds on specific model of computation such as DT,CC,polynomials,etc. -Aim at unconditional results.Complexity • Structural complexity: – High-level questions. – P vs. NP, P vs. BPP, P vs. PSPACE, etc. – Many conditional results. • Concrete complexity – Low-level questions. – Lower bounds on specific model of computation such as DT, CC, polynomials, etc. – Aim at unconditional results