Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Complexity versus Computability

Expand Messages
  • Lance
    To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology. Computability
    Message 1 of 1 , Jul 22, 2005
    • 0 Attachment
      To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology. Computability (Recursion) Theory started in the 1930's with the work of Turing, Church, Gödel and Kleene and complexity theory gathered steam in the 60's. Complexity theory derives many of its definitions from computability theory such as Turing machines, reducibility, completeness and lowness and the polynomial-time hierarchy is an analogue of the arithmetic hierarchy. Several complexity theorists originally received their Ph.D. in computability theory.

      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 University of Chicago has for many years a strong presence in computability theory led by Bob Soare who wrote a major textbook 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."

      --
      Posted by Lance to Computational Complexity at 7/22/2005 09:13:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.