FOM: priority arguments in applied recursion theory
Stephen Fenner
fenner at cs.sc.edu
Tue Aug 3 12:38:58 EDT 1999
> 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
More information about the FOM
mailing list