Aleksa Stankovic: Turing machines, NP-completeness of graph coloring, and circuit lower bounds
Time: Fri 2019-05-17 13.15 - 15.00
Location: Room 3418, Lindstedtsvägen 25, 4th floor, Department of Mathematics, KTH
Participating: Aleksa Stankovic
Which problems can be solved efficiently by our computers, and can we show that a certain problems are hard to solve? These two questions are the focal points of this talk.
We start by mathematically formalizing computation using Turing machines, after which we formalize what is "efficient" and which functions are interesting to compute, by introducing P and NP complexity classes. In order to explain how we can claim that the problem is hard, we will also introduce the concept of NP-completeness by sketching a proof of the Cook-Levin theorem, and use the results to prove that calculating the chromatic number of a graph is computationally difficult task.
Finally, if the time permits, through a discussion of the famous P versus NP problem we motivate circuit complexity theory and using Razborov-Smolensky method we prove some circuit lower bounds.
We start by mathematically formalizing computation using Turing machines, after which we formalize what is "efficient" and which functions are interesting to compute, by introducing P and NP complexity classes. In order to explain how we can claim that the problem is hard, we will also introduce the concept of NP-completeness by sketching a proof of the Cook-Levin theorem, and use the results to prove that calculating the chromatic number of a graph is computationally difficult task.
Finally, if the time permits, through a discussion of the famous P versus NP problem we motivate circuit complexity theory and using Razborov-Smolensky method we prove some circuit lower bounds.