Undergrad Complexity at CMU - Lecture 16: Space Complexity

preview_player
Показать описание
Undergraduate Computational Complexity Theory
Lecture 16: Space Complexity

Carnegie Mellon Course 15-455, Spring 2017

Taught by Ryan O'Donnell

Suggested reading: Sipser Ch. 8.0, 8.1 (just about L), 8.2

  1. Ryan O'Donnell
  2. Computational Complexity
  3. Complexity Theory
  4. CMU
  5. Carnegie Mellon
  6. Computer Science
Рекомендации по теме
Undergrad Complexity at 1:19:32

Undergrad Complexity at CMU - Lecture 1: Course Overview

Undergrad Complexity at 1:21:12

Undergrad Complexity at CMU - Lecture 16: Space Complexity

Undergrad Complexity at 1:21:04

Undergrad Complexity at CMU - Lecture 8: NP

Undergrad Complexity at 1:17:40

Undergrad Complexity at CMU - Lecture 23: The Polynomial Hierarchy

Undergrad Complexity at 1:20:28

Undergrad Complexity at CMU - Lecture 7: SAT

Undergrad Complexity at 1:19:47

Undergrad Complexity at CMU - Lecture 2: Turing Machines

Undergrad Complexity at 1:20:35

Undergrad Complexity at CMU - Lecture 26: Beyond Worst-Case Analysis

Undergrad Complexity at 1:21:41

Undergrad Complexity at CMU - Lecture 10: Reductions

Undergrad Complexity at 1:21:40

Undergrad Complexity at CMU - Lecture 21: Randomized Complexity: RP, coRP, and ZPP

Undergrad Complexity at 1:22:12

Undergrad Complexity at CMU - Lecture 27: Hardness within P

Undergrad Complexity at 1:21:12

Undergrad Complexity at CMU - Lecture 17: Savitch's Theorem and NL

Undergrad Complexity at 1:19:35

Undergrad Complexity at CMU - Lecture 22: BPP

Undergrad Complexity at 1:20:32

Undergrad Complexity at CMU - Lecture 12: NP-Completeness Reductions

Undergrad Complexity at 1:21:42

Undergrad Complexity at CMU - Lecture 6: Problems in P

Undergrad Complexity at 1:19:56

Undergrad Complexity at CMU - Lecture 13: Search-to-Decision, Padding, Dichotomy Theorems

Undergrad Complexity at 1:21:29

Undergrad Complexity at CMU - Lecture 15: coNP

Undergrad Complexity at 1:20:50

Undergrad Complexity at CMU - Lecture 5: Time Hierarchy Theorem

Undergrad Complexity at 1:22:02

Undergrad Complexity at CMU - Lecture 24: Oracle Turing Machines and P^NP

Undergrad Complexity at 1:16:03

Undergrad Complexity at CMU - Lecture 11: NP-Completeness and the Cook--Levin Theorem

Undergrad Complexity at 1:20:00

Undergrad Complexity at CMU - Lecture 28: Why is P vs. NP Difficult?

Undergrad Complexity at 1:21:05

Undergrad Complexity at CMU - Lecture 20: The Immerman--Szelepcsényi Theorem

Undergrad Complexity at 1:19:39

Undergrad Complexity at CMU - Lecture 19: From P-Completeness to PSPACE-Completeness

Undergrad Complexity at 1:21:02

Undergrad Complexity at CMU - Lecture 9: Nondeterminism

Undergrad Complexity at 1:23:37

Undergrad Complexity at CMU - Lecture 25: Interactive Proofs: IP=PSPACE

Комментарии
Автор

on the very last statement on the board, should it be ∃A ∈ SPACE(log^2 n), rather than TIME(log^2 n)?

molosist