One can say computational complexity is just computability theory with resource bounds but the fields feel quite different.

- Complexity theorists consider themselves part of the theoretical computer science community and find themselves mostly in CS departments. Recursion theorists consider themselves logicians and find themselves mostly in math departments.
- Complexity theorists try to understand efficient computation analogous to theoretical physicists trying to understand how the universe works, where computability theorists consider more ethereal questions of logical definability. Consider the example of quantum computing: Many complexity theorists analyze the computational power of these machines where quantum has had virtually no effect on computability theory.
- Outside of diagonalization, the tools and techniques used in the fields are completely different. Rare does one see a priority or finite injury argument in complexity, whereas algebra and combinatorics don't appear in most computability proofs.

The difference in thinking hit me during a logic seminar where the
speaker asked "How do we usually show that a language is
computable?" I thought *find an algorithm*. The speaker
answered his own question "Show that the language is c.e. and
co-c.e."

One major difference seems to be that computability theory has already finished all of its major work. Complexity theory, on the other hand, has dozens of open problems, some being of the utmost importance.

ReplyDeleteIs there even a single, imporant open problem left in computability theory?

I am sure there are many challenging open questions in computability theory. IMPORTANCE, however, may be in the eye of the beholder :-)

ReplyDeleteA major open problem in computability is whether or not the theory of the rationals is decidable.

ReplyDeleteThis seems to be a concrete algorithmic question that complexity theorists and TCS people could get interested in.

Most believe that the answer is "undecidable" and the approaches are very algebraic attempts to define the integers within the rationals. Of course, there might be a good reason why this approach has not yet provided the answer...

Open Problem of Importance: Is there an

ReplyDeleteautomorphism of the Turing Degrees

(nontrivial).

Computability theory was dying, and perhaps

still is (``its been dying for 20 years'')

but there are three things going on that

are trying to revive it.

a) Name Change- Soare has succeeded in getting people to call it

``Computability Theory'' instead of

``Recursion Theory''. I doubt this will

have much effect.

b) Connect up with other branches of Math

by analyzing foundational questions.

Anil Nerode's Recursive math program

(Computable Math now I guess) looked at

proofs in OTHER branches of math and

tried to prove when they can be made

effective and when they cannot.

Or find a weaker version of a theorem

that WAS effective.

(See HANDBOOK OF RECURSIVE MATHEMATICS.

The article of most interest to OUR

community might be mine on

Recursive Combinatorics.

on my website www.cs.umd.edu/~gasarch

or just email me for it)

ALSO Harvey Friedman's REVERSE MATH

program about seeing when various types

of axioms are needed to prove things.

(This overlaps with Recursive Math

but is actually different.)

c) Connect up to other fields of math by

actually helping them to solve some of

their problems. I once gave a talk

entitled ``Applications of Logic to

the rest of mathematics'' I had 5.

That was in 1984. There have been more

since then, but not alot more.

I've heard rumors of Algebraic Geometry

being helped by Model Theory.

And of Geometry being helped by

Computability theory. GREAT if it

actually works, but I am skeptical.

MISC: In the STRUCTURES CONFERENCE early days

there would be an ocasional paper

like `Theory of the p-m degrees is

undecidable' That kind of hard

recursion theory in complexity is gone

now.

On Fri Jul 22, 02:02:03 PM CDT, Gasarch wrote:

ReplyDeleteG: Soare has succeeded in getting people to call it "Computability Theory'' instead of "Recursion Theory''. I doubt this will have much effect.

BSA: Perhaps. However, I find that the consequences of accepting that there can be computable (decidable) functions (relations) that are instantiationally equal (equivalent) to some, but not identical to any, recursive function (relation) are far-reaching for both computability theory and computational complexity theory.

G: Connect up with other branches of Math by analyzing foundational questions.

BSA: Yes. As I see it, the challenge faced by standard interpetations of classical logic is that it has yet to comprehensively resolve some grey areas in foundational issues. For instance, such interpretations have not unequivocally answered the question of whether non-constructively defined mathematical concepts are identical to non-algorithmically defined mathematical concepts.

I find that if we diferentiate formally between the concepts of effectively decidable instantiational Tarskian-truth / Goedelian provability / completeness, and effectively decidable algorithmic Tarskian-truth / Goedelian provability / completeness, we can, indeed, bridge the gap between classical logic and computability that addresses the question of when proofs 'can be made effective and when they cannot'.

G: ... Harvey Friedman's REVERSE MATH program about seeing when various types of axioms are needed to prove things.

BSA: One way of viewing this is that introduction of an axiom to a Theory is simply formalisation of the postulation that a relation is effectively Tarskian-true instantiationally under any interpretation. Now, if the relation is not effectively Tarskian-true algorithmically under some interpretation of the Theory, then the axiom may be necessary since it cannot be proven inductively from the other axioms of the Theory.

G: Connect up to other fields of math by actually helping them to solve some of their problems.

BSA: I believe that this is - or at least it should be - the raison d'etre for the study of mathematics: to provide, and study how, a set of languages can, first, adequately express a correlation between an individual intelligent agents' abstract (i.e., Platonic) concepts, and precisely defined mathematical symbolism; and, second, effectively, and unambiguously, communicate (i.e., non-Platonically) as many of such correlations to other intelligent agents as is possible.

Regards,

Bhupinder Singh Anand

On 7:13 AM on Jul 22 2005 , Lance wrote:

ReplyDeleteLF: To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology.

BSA: The separation may be an illusion. A Computability Theorist may simply be a Computational Complexity Theorist who either refuses, or is reluctant, to follow Goedel's interpretation of his own reasoning, and accept that there is an unbridgeable gap not only between mathematical concepts that can be conceived Platonically and those can be communicated effectively, but also between what can be asserted as true in the interpretation of a formal theory, and what can be proved within the theory.

Regards,

Bhupinder Singh Anand

This reminds me - M.O. Rabin showed in 1957 that there exist games with winning strategies that are not computable. The reference is

ReplyDeleteRabin, M. "Effective Computability of Winning Strategies," in Contributions to the Theory of Games III (Annals of Mathematical Studies 39): 147-157

or you can see a statement of the theorem and proof as part of

http://www.qmul.ac.uk/~ugte176/

seminars/Comput-Complex1.pdf

(sorry, line break in above URL)

I've always wondered what would have happened if the notion of resource bounds had been applied to this result. Would we have seen today's sort of algorithmic game theory and computational complexity work in e-commerce much earlier? (or were they applied and I just don't know about it?)

It seems to me a lot of people drawn to Complexity Theory insist on looking at it in exclusively computational terms. For example, finite model theory provides nice logical characterizations of comon complexity classes (P, NP, PSPACE). But it seems like there are very few researchers trying to take advantage of these ideas.

ReplyDelete

ReplyDeleteIt seems to me a lot of people drawn to Complexity Theory insist on looking at it in exclusively computational terms.I think the Toronto group has been one exception, trying many different approaches at once.

I don't know what the anonymous poster had in mind when he said: "A major open problem in computability is whether or not the theory of the rationals is decidable. This seems to be a concrete algorithmic question that complexity theorists and TCS people could get interested in. Most believe that the answer is "undecidable" and the approaches are very algebraic attempts to define the integers within the rationals. Of course, there might be a good reason why this approach has not yet provided the answer..."

ReplyDeleteIn her Ph.D. thesis in 1948, Julia Robinson proved that the theory of the rationals using plus and times is undecidable. She proved this by showing that it is possible to define the integers within the rationals.

Ron: the anonymous poster was probably referrinmg to the question of whether the _existential_ theory of the rationals is decidable, i.e. Hilbert's 10th problem over Q. This actually is still open AFAIK.

ReplyDelete