SEMINARIOS EN INGENIERÍA
INFORMÁTICA Y DE TELECOMUNICACIÓN 2006-2007
Doctorado en Ingeniería
Informática y de
Telecomunicación
Programa Oficial de Posgrado en
Ingeniería Informática y de Telecomunicación
Escuela Politécnica Superior, Universidad Autónoma de
Madrid
14 de diciembre de 2006, 12:00
Salón de Grados, Escuela Politécnica Superior,
Universidad Autónoma de Madrid
Computational
Complexity: an overview of open problems.
Michael Soltys
Department of
Computing and Software
McMaster University
(Hamilton, Canada)
Abstract
Computational Complexity Theory is a major research area of Computer
Science. Its aim is to establish mathematical foundations of
efficient
computation. All agents/machines involved in performing a
computational task have limited resources (such as time, memory,
communication, etc.). Computational complexity asks which tasks
can be
performed under such limitations.
There has been a significant development in the last 30 years. It
has become clear that studying the limits of given computational
resources leads to a new understanding of old and well established
concepts, such as proof, knowledge representation, the nature of
randomness, and especially cryptography.
In this talk we shall give an overview of the field, mention some
of the latest results, and present many of the open problems, starting
with the difficult and fundamental question of P versus NP.
Michael Soltys
Michael Soltys is an associate professor in the department of
Computing and Software at McMaster University, in Hamilton,
Canada. He
has completed his PhD in 2001 at the University of Toronto, under the
supervision of Stephen Cook.