FOM: Complexity Theory

[Joseph Shoenfield]

     Martin Davis writes:
     >I disagree with Joe when he says that the methods (of complexity
theory and recursion theory) are similar.   My sense (and I'm not such an
expert) is that the arguments in complexity theory tend to be
down-and-dirty combinatorial in nature.
     Martin, you are as much an expert on this question as I am, and you
are certainly right about much of complexity theory, e.g., Cook's
ground-breaking result that the satisfaction problem for the propositional
calculus is NP complete.   But there are some exceptions.   I spent some
time looking at complexity theory about ten years ago (only yesterday).
The result which pleased me most was a theorem of Mahaffey, which says
that if P=NP is false, no sparse set is NP-complete.   A sparse set is a
set of words such that the number of words of length n in the set is
bounded by a polynomial in n.   This is clearly in the spirit of Post's
program to use the size of a set to show that it is not complete in some
sense.   Unlike all of Post's results, it uses smallness rather than
largeness.   The proof is quite pleasing; difficult enough to be
interesting, but intuitive and clear in its basic ideas.   The techniques
include some standard techniques, some techniques developed by other
complexity theorist in proving weaker version of the result, and some
techniques which he developed.  If I had found more theorems like this, I
might have been tempted to do some research in complexity theory.