CSE104, Lec 9: Savitch's theorem, PSPACE = NPSPACE

preview_player
Показать описание
A discussion of the basic bounds on relating time and space complexity classes. Savitch's theorem and why PSPACE = NPSPACE
  1. C. Seshadhri
Рекомендации по теме
CSE104, Lec 9: 1:25:23

CSE104, Lec 9: Savitch's theorem, PSPACE = NPSPACE

mod03lec16 - Savitch's 0:28:23

mod03lec16 - Savitch's Theorem

Theory of Computation: 0:26:04

Theory of Computation: Savitch's Theorem [Unedited Version]

17. Space Complexity, 1:20:10

17. Space Complexity, PSPACE, Savitch's Theorem

W12L66_Savitch's theorem 0:26:28

W12L66_Savitch's theorem

Komplexität #33 - 0:20:40

Komplexität #33 - Satz von Savitch (PSpace = NPSpace)

CS4510 L17A Savitch's 0:43:57

CS4510 L17A Savitch's Theorem

CSE104, Lec 13: 1:24:02

CSE104, Lec 13: NL = co-NL, the Immerman-Szelepcsenyi theorem

CSE104, Lec 12: 1:22:14

CSE104, Lec 12: Read-once certificates for NL, starting NL=co-NL

Computer Science: The 0:02:12

Computer Science: The crux of Savitch's Theorem

UHAMPATH, PSPACE, Savitch's 0:57:42

UHAMPATH, PSPACE, Savitch's Theorem - CSE355 Intro Theory of Computation 8/01 Pt. 2

Space-unconstructable function in 0:02:17

Space-unconstructable function in the proof of Savitch's theorem

Savitch's theorem: sketch 0:01:39

Savitch's theorem: sketch of proof (in less than 2min!)

CS422 Theory of 1:13:08

CS422 Theory of Computation, Chapter 5c

Prove and Explain 0:12:59

Prove and Explain Savitch's Theorem and non deterministic space

Theory of Computation 1:21:43

Theory of Computation (CS6160) Lecture 09 (Part 2 of 2), Professor Gabriel Robins

TQBF PSPACE-complete, Space 1:02:58

TQBF PSPACE-complete, Space Hierarchy Theorem - CSE355 Intro Theory of Computation 8/03 Pt. 1

Theory of Computation 1:23:06

Theory of Computation (CS6160) Lecture 09 (Part 1 of 2), Professor Gabriel Robins

complexity theory: Time 0:15:01

complexity theory: Time Hierarchy theorem and Space Hierarchy theorem

Satz von Immerman 0:27:02

Satz von Immerman und Szelepcsényi

Basic Complexity class: 0:24:44

Basic Complexity class: P, NP, PSPACE and EXP classes

Time hierarchy theorem 0:08:05

Time hierarchy theorem

Blum's speedup theorem 0:01:34

Blum's speedup theorem

Undergrad Complexity at 1:20:21

Undergrad Complexity at CMU - Lecture 18: NL-Completeness and Logspace Reductions

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

15:15 This is interesting. My book says O(2^f(n)) but it could be wrong. Anyway, you say that a configuration is a string of length s(n) over alphabet Σ ∪ Q, but that's not entirely true. Yes, Σ could be binary and Q a set with a larger amount of symbols, but in any configuration string only one symbol of the string is a Q-symbol. So there are a large amount of combinations over the alphabet that are unacceptable strings: all those with more than one Q-symbol. Actually, for s(n) large enough, I think we can assume the alphabet simply binary because only one Q-symbol is negligible. What you think?

willayou