FOM: Priority arguments in complexity (also RFT in inductive inference)

John Case case at mail.eecis.udel.edu
Fri Sep 4 15:12:41 EDT 1998

My favorite priority arguments in complexity theory are in

@inproceedings{        Kur-Mah-Roy:b:90:selman,
editor =        "Selman, A.",
author =        "Kurtz, S. and Mahaney, S. and Royer, J.",
title =         "The Structure of Complete Degrees",
booktitle =         "Complexity Theory Retrospective",
pages =         "108--146",
publisher =     "Springer-Verlag, NY",
year =          1990}

AND

@article{   Che-Hom:m:98,
author =        "Z. Chen and S. Homer",
title =         "The Bounded Injury Priority Method and the Learnability of
Unions of Chains of Rectangles",
note =        "Preprint at
http://cs-www.bu.edu/faculty/homer/papers/apal.ps",
year =          1998}

However, my own taste for RFT in complexity theory runs more toward fancy (and
computationally feasible) recursion theorems of the program self (and other)
reference type. (-8  See:

@book{          Roy-Cas:b:94,
author =        "Royer, J. and Case, J.",
title =         "Subrecursive Programming Systems: Complexity and
Succinctness" ,
series =         "Research monograph in
Progress in Theoretical Computer Science" ,
publisher =     "{Birkh\"auser}~Boston",
year =          1994}

AND

@article{Cas:j:91,
author =        "J. Case",
year =          "{ 1991}",
title =         "Effectivizing Inseparability",
journal =       "Zeitschrift {f\"ur} Mathematische Logik und
Grundlagen der Mathematik",
volume=         37,
pages =         "97-111"}

In \cite{Roy-Cas:b:94} we develop and use (\cite{Roy-Cas:b:94,Cas:j:91})
a Hybrid Recursion Theorem. This permits, for {\em example\/} self and other
reference between a system for the multitape Turing machine programs
explicitly clocked to halt in a quadratic in the length of their inputs and a
system for the functions partial recursive in the halting problem.  In this
way some of the subrecursively difficult combinatorics can be trivially handled
in the latter system, a system where $Sigma_2^0$ requirements may be expressed,
etc.  I suppose constructions with more complex requirements in the future
might be handled with full blown priority arguments --- but in the super (not
the sub) recursive system. (-8  BTW, in the Hybrid Recursion Theorem examples,
the subrecursive program(s) constructed can make some sense of the I/O behavior
of their super recursive counterparts thanks to the result, generalizing Post
and others, that each function partial recursive in the halting problem is
uniformly the limit of a suitable linear-time computable function
\cite{Roy-Cas:b:94}.

John Case

PS: I note too that there have been and are now researchers (the so called
inductive inference community) within computational learning theory
(researchers mostly in the US, Germany and Latvia, but with representation in
at least Asia and Australia) who apply recursive function theory {\em methods}
in this area.  Many of these people are employed in computer science
departments, but some are employed in mathematics or other departments.
See:  the Appendix in Odifreddi's upcoming? second volume on RFT; the COLT,
EuroCOLT, and ALT proceedings; and the first edition of Osherson, Stob and
Weinstein's {\em Systems That Learn}, MIT Press, 1986.  The second edition,
co-authored by Jain, S., Osherson, D., Royer, J., and Sharma, A., also with
MIT Press, is to appear soon.  I note too that the CMU philospher, Kevin
Kelly, treats, among other things, this RFT approach to inductive inference in
his {\em The Logic of Inquiry}, Oxford Press, 1996. (-8  JC