Definitions of Computational Complexity in Analysis

Presenter: Robert Rettinger University of Applied Sciences and Arts Dortmund
  • Date: Thursday, 15 March 2018 to Thursday, 15 March 2018
  • Time: 03:00PM to 04:00PM
  • Location: Jack Erskine, Room 111, Ilam Campus
  • Ticket: Free

We will discuss several definitions of complexity in analysis based on the type-2-Turing-machine model, i.e. by using approximations.

Whereas the definition of computability in analysis based on the type-2-Turing-machine model gives us a robust and widely accepted notion, a similar natural definition of complexity seems to be much harder to find. The basic, naive definition of complexity is probably the most natural one. Unfortunately, this basic definition is applicable only for a restricted class of simple problems.

On the other side there is a widely applicable definition of polynomial time complexity, recently introduced by Kawamura and Cook, based on type-2-polynomials. We will discuss some arguments in favour of and against this definition. Additionally, we will give a slightly modified definition of complexity which overcomes some of the problems of type-2-polynomials.

We aim to start a discussion on the notion of complexity rather than giving perfect definitions.

All welcome.

More Events