Computability and Complexity from a Programming Perspective

Neil D. Jones
University of Copenhagen

The author's forthcoming book proves central results in computability and complexity theory from a programmer-oriented perspective. In addition to giving more natural definitions, proofs and perspectives on classical theorems by Cook, Hartmanis, Savitch, etc., some new results have come from the alternative approach.

One: for a computation model more natural than the Turing machine, multiplying the available problem-solving time provably increases problem-solving power (in general not true for Turing machines). Another: the class of decision problems solvable by Wadler's "treeless" programs, or by cons-free programs on Lisp-like lists, are identical with the well-studied complexity class LOGSPACE.

A third is that cons-free programs augmented with recursion can solve all and only PTIME problems. Paradoxically, these programs often run in exponential time (not a contradiction, since they can be simulated in polynomial time by memoization). This tradeoff indicates a tension between running time and memory space which seems worth further investigation.


Neil D. Jones

DIKU, University of Copenhagen
Universitetsparken 1
2100 Copenhagen East
Denmark
Email:neil@diku.dk
Home page: http://www.diku.dk/people/NDJ.html

Back to the list of talks