Undergrad Complexity at CMU - Lecture 6: Problems in P

preview_player
Показать описание
Undergraduate Computational Complexity Theory
Lecture 6: Simulations and Turing Machine Variants

Carnegie Mellon Course 15-455, Spring 2017

Taught by Ryan O'Donnell

Suggested reading: Sipser Ch. 7.2 (about PATH, and RELPRIME if you like)

  1. Ryan O'Donnell
  2. Computational Complexity Theory
  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:17:40

Undergrad Complexity at CMU - Lecture 23: The Polynomial Hierarchy

Undergrad Complexity at 1:21:04

Undergrad Complexity at CMU - Lecture 8: NP

Undergrad Complexity at 1:20:28

Undergrad Complexity at CMU - Lecture 7: SAT

Undergrad Complexity at 1:20:32

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

Undergrad Complexity at 1:21:40

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

Undergrad Complexity at 1:21:41

Undergrad Complexity at CMU - Lecture 10: Reductions

Undergrad Complexity at 1:21:12

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

Undergrad Complexity at 1:20:35

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

Undergrad Complexity at 1:22:12

Undergrad Complexity at CMU - Lecture 27: Hardness within P

Undergrad Complexity at 1:19:47

Undergrad Complexity at CMU - Lecture 2: Turing Machines

Undergrad Complexity at 1:21:42

Undergrad Complexity at CMU - Lecture 6: Problems in P

Undergrad Complexity at 1:19:35

Undergrad Complexity at CMU - Lecture 22: BPP

Undergrad Complexity at 1:21:29

Undergrad Complexity at CMU - Lecture 15: coNP

Undergrad Complexity at 1:19:56

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

Undergrad Complexity at 1:21:05

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

Undergrad Complexity at 1:22:02

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

Undergrad Complexity at 1:20:00

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

Undergrad Complexity at 1:16:03

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

Undergrad Complexity at 1:21:02

Undergrad Complexity at CMU - Lecture 9: Nondeterminism

Undergrad Complexity at 1:19:39

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

Undergrad Complexity at 1:17:57

Undergrad Complexity at CMU - Lecture 4: Time Complexity and Universal Turing Machines

Undergrad Complexity at 1:20:50

Undergrad Complexity at CMU - Lecture 5: Time Hierarchy Theorem

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

41:30 about runtime greedy-2COL. if you have traversed all edges there is no need to continue the algorithm, since any colouring of remaining vertices is acceptible. Hence, if you keep track on wich edges are traversed and allways start a component at a vertex with an edge, the compute time should only depend on the nr of edges... or am I missing something?

orvarl-o