[Date Index] [Thread Index] [FOM Postings] [FOM Home]

*To*: Stephen G Simpson <simpson@math.psu.edu>*Subject*: Re: FOM: priority arguments in applied recursion theory*From*: Stephen Fenner <fenner@cs.sc.edu>*Date*: Mon, 26 Jul 1999 16:44:06 -0400 (EDT)*cc*: fom@math.psu.edu, Rod Downey <Rod.Downey@MCS.VUW.AC.NZ>*In-Reply-To*: <14231.47146.661199.79846@mordred.cs.utk.edu>*Sender*: owner-fom@math.psu.edu

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@cs.sc.edu Columbia, SC 29208 USA Web: http://www.cs.sc.edu/~fenner

**Follow-Ups**:**Stephen G Simpson**- FOM: priority arguments in applied recursion theory

**References**:**Stephen G Simpson**- FOM: priority arguments in applied recursion theory

[Date Prev] [Date Next] [Thread Prev] [Thread Next]

[Date Index] [Thread Index] [FOM Postings] [FOM Home]