Skip to main content

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.