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

• Computational Learning Theory,
  

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

• Machine Self-Reference.
  

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.

---

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

(1) P2-program e decides the finite set A,
(2) Peano Arithmetic proves P2-program e's explicit quadratic run time bound,
(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:

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

• Effectivizing Inseparability, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 37 (1991), 97-111. 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 0-8176-3767-2, Phone: 1-800-777-4643, Department Y807, P.O. Box 2485, Secaucus, NJ 07096-2485 USA. Click HERE for associated errata.
  

---

• My Research Page
  
• My Homepage
  
• My Site Map
  
• To UD's CIS Department's Homepage
  
• To UD's Cognitive Science Homepage
  
• To UD's Homepage
  
• case@cis.udel.edu
  
  Glimpse Search My of Pages on www.cis.udel.edu: