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.

Somehow, I had missed this news. Paul was not only an excellent mathematician, but he was also a wonderful man. I also heard great reviews of his performance as a department chair at the University of Washington.

ReplyDelete