FOM: priority arguments in applied recursion theory

[Stephen Fenner]

On Thu, 22 Jul 1999, Stephen G Simpson wrote:

> Rod Downey (FOM, 22 Jul 1999 12:17:13) argues against what has now
> come to be called Simpson's Thesis, i.e., my observation (FOM, 21 Jun
> 1999 21:36:37) that
> 
>   ``priority methods are almost completely absent from applied
>   recursion theory.''
> 
> ...
> 
> Furthermore, priority arguments also seem to play a very small or
> nonexistent role in the other ``applied'' areas that I mentioned:
> 
> ...
>
>   theoretical computer science (At least the standard textbooks on
>     computational complexity etc do not use priority arguments.)
>
> ...
>
> As for computer science, obviously the standard textbooks do not use
> priority arguments (look in the computer science section in your
> campus bookstore), ...
> 

Theoretical computer science is an area where the ratio of papers to books
is still pretty high.  Here are two examples of priority arguments in
complexity theory that I know of:

 H. Buhrman and L. Torenvliet, "On the cutting edge of relativization: The
 resource-bounded injury method."  Proceedings of the ??th EATCS
 International Conference on Automata, Languages, and Programming, 1994.
 (draft at http://www.cwi.nl/~buhrman/PAPERS/oracle.ps.gz)

 S. Fenner, S. Kurtz, and J. Royer, "Every polynomial-time 1-degree
 collapses iff P = PSPACE."  Proceedings of the IEEE Symposium on the
 Foundations of Computer Science, 1989.  (somewhat recent draft at
 http://www.cs.sc.edu/~fenner/papers/1degrees.PS, updated draft to appear
 shortly)

BT use a priority argument to find an oracle relative to which all
nondeterministic exponential-time sets are NP-easy.  The result was
subsequently proven without a priority argument
(http://www.cs.sc.edu/~fenner/papers/nexp.PS), but the original priority
argument has great heuristic value.  In FKR, a priority argument is used
to prove Lemma 20, a technical lemma which is used several times elswhere
in the paper.  We never actually mentioned the phrase "priority argument"
when describing the proof, but it is one nonetheless.

Stephen Fenner                       Phone: 803-777-2596
Computer Science Department          FAX:   803-777-3767
University of South Carolina         Email: fenner at cs.sc.edu
Columbia, SC  29208  USA             Web:   http://www.cs.sc.edu/~fenner