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
For the sample result just below: DTIME(n^k) is (by definition) the set of functions each computable on a deterministic, multi-tape Turing machine 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 above). 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:
OTHER REPRESENTATIVE PUBLICATIONS: