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.
in the area. I sat in Soare's class in the
hope some of the techniques in computability would help my research in
complexity (for the most part they haven't) and have gone to a few
logic seminars. Everything I do they call "zero."
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.
ReplyDeleteIt seems to me a lot of people drawn to Complexity Theory insist on looking at it in exclusively computational terms.
ReplyDeleteI 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.