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, 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.


Enter/submit your email address to receive Email Notification
when this Publications Section of this Complexity/Succinctness page is Updated:

March 29, 2013
John Case