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.
Poutama. level 3, Puaka James Hight, University of Canterbury
Sunday 15 July 2018, 12:30PM
Recital Room, 3 Hereford Street , UC Arts - City Location, Arts Centre of Christchurch
Wednesday 26 September 2018, 07:00PM
Jack Erskine 235, University of Canterbury
Wednesday 28 February 2018, 12:30PM
Business and Law 526, Ilam campus
Tuesday 3 April 2018, 04:30PM
Recital Room, UC Arts City Location, Arts Centre of Christchurch, 3 Hereford Street
Friday 28 September 2018, 01:10PM