Computer Sciences Colloquium - DESCRIPTIVE COMPLEXITY: USING LOGIC TO UNDERSTAND COMPUTATION

Abstract

Most computational problems can be understood as computing a function from n-bit inputs to m-bit outputs. The bits of the output are properties of the input. It is striking that the computational complexity of computing the function in terms of time, space, number of processors, etc., can be completely understood via the expressive power of the logical language needed to describe these properties. This will be an accessible talk explaining descriptive complexity and the resulting insights gained. I will end by describing some of the progress achieved by many researchers over the last 5 years.