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.
Classics Public Talk: SPQR SNAFU: Mutiny and Indiscipline in the Roman Army of the Late Republic and Early Empire
Recital Room, UC Arts - City Location, Arts Centre of Christchurch, 3 Hereford Street
Thursday 4 October 2018, 06:00PM
Ernest Rutherford 140, University of Canterbury
Friday 6 July 2018, 02:00PM
Okeover 106, Okeover House
Friday 12 October 2018, 12:00PM
Recital Room, 3 Hereford Street , UC Arts - City Location, Arts Centre of Christchurch
Wednesday 26 September 2018, 07:00PM