Complexity/Succinctness (to be updated soon)
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
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, multi-tape
within time bounded by a k-th 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.
Let P1 be an arbitrary programming system for DTIME(n), let P2 be a
programming system for DTIME(n^2) based on explicitly clocked, multi-tape
Turing Machines. (P1 and P2 are mentioned
Let T be a true, deductively closed, recursively
axiomatizable, first-order theory which includes Peano Arithmetic.
Then, for each total (and possibly very fast-growing) function h recursive
in the halting problem, there are associated finite set A and
P2-program e such that:
(1) P2-program e decides the finite set A,
(2) Peano Arithmetic proves P2-program e's explicit quadratic run time
(3) h(the size of e) < the size of a smallest P1-program for deciding A,
(4) P2-program e actually runs within time linear in the length
of its inputs, but
(5) the theory T cannot prove that P2-program e runs within linear time.
OTHER REPRESENTATIVE PUBLICATIONS:
Zeitschrift fur Mathematische Logik und Grundlagen der
Mathematik, 37 (1991), 97-111. Click
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 &
J. Royer), research monograph
in the series Progress in Theoretical
Birkhauser Boston, 1994, 251pp, Hardcover $49.50,
ISBN 0-8176-3767-2, Phone: 1-800-777-4643,
Department Y807, P.O. Box 2485,
Secaucus, NJ 07096-2485 USA.
HERE for associated errata.
March 29, 2013