Complexity/Succinctness
Complexity/Succinctness (to be updated soon)
N.B.
HERE is a link to a complete, uptodate
(as of March 18, 2009) list of my publications,
including those on Program Complexity & Succinctness.
This project involves the development of
general purpose recursion and complexity theoretic
tools for working with low level subrecursive programming systems such as
P1 and P2
below, applying these tools in
structural complexity theory and in
and using them to prove many new theorems
(including the sample below from my research monograph with
Jim Royer
mentioned
further below) regarding program size and complexity.
The tools include computationally inexpensive
For the sample result just below:
DTIME(n^k) is (by definition) the set of
functions each computable on a deterministic, multitape
Turing
machine
within time bounded by a kth degree polynomial in the length of its input.
The size of a program is (by definition) the total number of
characters in that program's text.
SAMPLE THEOREM:
Let P1 be an arbitrary programming system for DTIME(n), let P2 be a
programming system for DTIME(n^2) based on explicitly clocked, multitape
Turing Machines. (P1 and P2 are mentioned
above).
Let T be a true, deductively closed, recursively
axiomatizable, firstorder theory which includes Peano Arithmetic.
Then, for each total (and possibly very fastgrowing) function h recursive
in the halting problem, there are associated finite set A and
P2program e such that:
(1) P2program e decides the finite set A,
(2) Peano Arithmetic proves P2program e's explicit quadratic run time
bound,
(3) h(the size of e) < the size of a smallest P1program for deciding A,
(4) P2program e actually runs within time linear in the length
of its inputs, but
(5) the theory T cannot prove that P2program e runs within linear time.
OTHER REPRESENTATIVE PUBLICATIONS:

Effectivizing Inseparability,
Zeitschrift fur Mathematische Logik und Grundlagen der
Mathematik, 37 (1991), 97111. Click
here
for a version which corrects some typos in the journal version.

Click here for Table of Contents and Chapter 1 of:
Subrecursive Programming Systems: Complexity &
Succinctness
(with
J. Royer), research monograph
in the series Progress in Theoretical
Computer Science,
Birkhauser Boston, 1994, 251pp, Hardcover $49.50,
ISBN 0817637672, Phone: 18007774643,
Department Y807, P.O. Box 2485,
Secaucus, NJ 070962485 USA.
Click
HERE for associated errata.
March 29, 2013
John Case