Undergrad Complexity at CMU - Lecture 10: Reductions

Undergraduate Computational Complexity Theory
Lecture 10: Reductions

Carnegie Mellon Course 15-455, Spring 2017

Taught by Ryan O'Donnell

Suggested reading: Sipser first half of Ch. 7.4 (and also Ch. 5.3 if it helps)

[AJ-vxzk]

@53:30, why is the statement false for the 4-chromatic number <=^p_T reduction (turing reductions)? Is it because the result is flipped for \phi_3? I though since the reduction is polynomial, one could just invoke the non-deterministic decision procedure for \phi_4 and \phi_3, this would make it in non-deterministic polynomial time?

[RahulMadhavan]

@54:12 please consider online users when clearing the board! :-)