Definitions of Computational Complexity in Analysis
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.
E6, Engineering Core, University of Canterbury, Ilam
Wednesday 18 July 2018, 05:30PM
Recital Room, UC Arts City Location, Arts Centre of Christchurch, 3 Hereford Street
Monday 15 October 2018, 03:30PM
Poutama, level 3, Puaka James Hight, University of Canterbury
Thursday 5 July 2018, 12:30PM
Recital Room, UC Arts City Location, Arts Centre of Christchurch, 3 Hereford St
Monday 16 July 2018, 03:30PM