FOM: where to put complexity theory

[Wayne Richter]

I have been enjoying (from a distance!) the discussion and 
feeling rather guilty whenever Steve laments the absence of
recursion theorists.  So here goes:

>From the mathematical point of view, I believe that complexity theory
should as it currently stands, be considered a part of recursion theory.
(There may be other more practical reasons why they are to be
separated.)
I am using "recursion theory" here in a rather broad sense, to include
not just degrees of unsolvability, but also subjects which go under  
the names of "generalized recursion theory", "recursive functionals of
finite types", "inductive definability", etc.

As Joe has mentioned, some form of definability is at the heart of
recursion theory, and quite similar notions of definability seem to
be at the heart of complexity theory as well.  The formulation of
some of the main problems of complexity theory in terms of finite
model theory is important here.  Moschovakis' theory of elementary
induction on abstract structures is a good example.  Although he
developed the theory on infinite structures, a non-trivial amount of
the theory goes through for finite structures as well. Some of the work
of Immerman and Gurevich and Shelah on finite structures is a natural
byproduct of this general theory of inductive definability.

 The basic open question of whether or not on finite structures,

$\Pi^1_1=\Sigma^1_1$,                                          (1) 

is easily formulated in terms of inductive
definability in several ways. For example, consider the statement

$IND(\Sigma^1_1)=monIND(\Sigma^1_1)$                           (2)

(i.e. that MONOTONE $\Sigma^1_1$ inductive definitions are just as
powerful as $\Sigma^1_1$ inductive definitions.) On finite structures
(2) is (easily seen to be) equivalent to (1).  On infinite structures
 such as $(\omega,<)$, (2) is a well known theorem with a number of
interesting, nontrivial proofs.

The solution to the basic open problems in complexity theory may
turn out to be completely irrelevant to the other parts of recursion
theory.  On the other hand the solutions may lead to new insights
into other parts of recursion theory and lead to a new explosion of
results. For now, there is a sufficiently strong connection to keep
them together.
Why don't we just wait and see what happens?!

Wayne Richter