FOM: priority arguments in applied recursion theory

[Stephen Fenner]

> Kurtz said:
> 
>  > I don't have a reference for Homer-Maass close at hand.  I'm sure
>  > that Steve can provide.
> 
> Is this referring to Steve Fenner, or to me?  If it's me, then I am at
> a loss, because I wasn't part of what was apparently an earlier
> discussion of Homer-Maass between Soare and Kurtz.

Not me, must be Steve Homer, who I think is still on the FOM list.

>  > By using a priority argument, we were able to demonstrate that a
>  > collapsing degree exists in exponential time
> 
> This together with Fenner's FOM posting of 26 Jul 1999 16:44:06 seems
> to suggest that collapsing degrees are one area of computational
> complexity theory where priority arguments play a significant role.
> Are there other such areas?  

Not that I'm aware of.

>  > what about the ratio of papers in theoretical computer science (or
>  > perhaps even computational complexity theory) that use priority
>  > arguments, to those that don't?  My impression is that this ratio
>  > is rather small.  Is it as high as 1/10 of a percent?  

It certainly is very small.  This could be for at least two reasons:

  1.  Priority methods just aren't that useful in complexity theory;
  2.  They would be more useful, but most complexity theorists don't
      know/aren't comfortable with them.

There's no remedy for (1), but (2) is closer to my experience.  It took me
a long time to get comfortable with even the simpler ones, say,
finite-injury 0' methods, but when I did, it helped me to see possible
applications that I hadn't before.

Steve