\documentclass[a4paper]{article}
\usepackage{amssymb}
\pagestyle{empty}
\hoffset=-40pt
\voffset=-20pt
\textwidth 15.3cm
\textheight 22cm % to fit our printers
\begin{document}

\begin{center}
{\huge Computability and Complexity from a 
Programming Perspective}\end{center}
         \begin{center}{\large Neil D. Jones}\end{center}
\begin{center}{\large DIKU, University of Copenhagen}\end{center}

\bigskip

The author's new 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
this approach.

One: for a computation model more natural 
than the Turing machine,
multiplying the available problem-solving 
time by a constant factor
provably increases problem-solving power 
(in general {\em not true} for
Turing machines).

Another: the class of decision problems 
solvable by {\em cons-free}
programs on Lisp-like lists, or by Wadler's 
``treeless" programs, are
identical with the well-studied 
complexity class LOGSPACE.

A third: cons-free programs augmented with 
recursion can solve {\em 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.

Other new perspectives that result from 
the programming approach include a
series of natural complete problems for 
PTIME, NPTIME and PSPACE, all based
on Boolean programs; a version of G\"odel's 
incompleteness theorem; and a
comprehensible proof of Levin's theorem: 
that for any search problem which
is efficiently checkable, one can construct 
a ``witness program'' which is
optimal up to a constant factor.

\end{document}