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.
Jack Erskine 235, University of Canterbury
Wednesday 28 February 2018, 12:30PM
Teece Museum of Classical Antiquities, UC Arts - City Location, Arts Centre of Christchurch, 3 Hereford Street
Wednesday 3 October 2018, 03:00PM
Ernest Rutherford room 141, Ernest Rutherford building
Monday 19 February 2018, 09:00AM
PSYC/SOCI Room 252, Ilam Campus, University of Canterbury
Friday 4 May 2018, 03:00PM
Areas beyond National Jurisdiction under the 1982 United Nations Convention of the Law of the Sea: Prospects and Progress
Undercroft 101, Puaka James Hight , University of Canterbury
Tuesday 25 September 2018, 05:30PM