Theorist Paul R Young passed away

In the early days of theoretical computer science, say 1960-1990 the main tools used were logic.
This made sense since, early on:

a) Some of the basic notions like DTIME(T(n)), P, NP used Turing Machines in their definitions

b) Some of the basic notions like reductions were modeled after similar concepts in
computability theory.

One of the people who did much work in the interface between Logic and TCS was Paul Young.
He passed away in December. Here are some highlights of his work:

1) One of the first books that covered both computability and complexity:

An Introduction to the general theory of Algorithms
by Machtey and Young.

2) In Computability theory all many-one complete sets are computably isomorphic. Berman and
Hartmanis conjectured that the poly-many-one degree of the NP-complete sets was the same. This
would mean that all NP-complete sets were poly-isom (all of the known ones are).

Mahaney and Young in the paper

Reductions Among Polynomial Isomorphism Types

showed that every many-one poly degree either has one degree or has an infinite number of
degrees in a very complicated way.

3) Recall that a Cook Reduction from A to B allows many queries to B, whereas a Karp Reduction
only allows one query and your answer must be the same sense as the query.
Are there  cases where a Cook reduction is faster? Yes, from the paper

Cook reducibility is faster than Karp Reducibility

by Longpre and Young

(The original title was going to be Cook is Faster than Karp, but it was changed since it invoked
images of Cook and Karp in a footrace.  Hmmm. Which one would be faster?)


4) The Boolean Hierarchy is a hierarchy of iterations of NP sets. What if instead of starting with P
one started with RP (Randomized Poly time). What an intriguing notion! To find out read


Generalized Boolean Hierarchies over RP

by  Alberto Bertoni, Danilo Bruschi, Deborah Joseph, Meera Sitharam, Paul Young

5) There are many more, mostly on the theme of the interaction of logic and computer science.

                       I saw him speak on some of these topics and was inspired by how much one could
take notions of computability and translate them into complexity theory.  The field has gone in a
different direction since then (more combinatorial) but we still use many of the basic concepts
like reducibility.  As such we all owe a debit to Paul Young.