tag:blogger.com,1999:blog-3722233.post112204171200653603..comments2021-09-21T04:14:03.225-05:00Comments on Computational Complexity: Complexity versus ComputabilityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-1122980123780840062005-08-02T05:55:00.000-05:002005-08-02T05:55:00.000-05:00Ron: the anonymous poster was probably referrinmg ...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.Janhttps://www.blogger.com/profile/01545309650727802288noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122954125663923592005-08-01T22:42:00.000-05:002005-08-01T22:42:00.000-05:00I don't know what the anonymous poster had in mind...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..." <BR/><BR/>In 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122561603998309892005-07-28T09:40:00.000-05:002005-07-28T09:40:00.000-05:00It seems to me a lot of people drawn to Complexity...<I> It seems to me a lot of people drawn to Complexity Theory insist on looking at it in exclusively computational terms.</I><BR/><BR/>I think the Toronto group has been one exception, trying many different approaches at once.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122403964430462472005-07-26T13:52:00.000-05:002005-07-26T13:52:00.000-05:00It seems to me a lot of people drawn to Complexity...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122284655016891772005-07-25T04:44:00.000-05:002005-07-25T04:44:00.000-05:00This reminds me - M.O. Rabin showed in 1957 that t...This reminds me - M.O. Rabin showed in 1957 that there exist games with winning strategies that are not computable. The reference is<BR/><BR/>Rabin, M. "Effective Computability of Winning Strategies," in Contributions to the Theory of Games III (Annals of Mathematical Studies 39): 147-157<BR/><BR/>or you can see a statement of the theorem and proof as part of<BR/><BR/>http://www.qmul.ac.uk/~ugte176/<BR/>seminars/Comput-Complex1.pdf<BR/><BR/>(sorry, line break in above URL)<BR/><BR/>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?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122135771574662772005-07-23T11:22:00.000-05:002005-07-23T11:22:00.000-05:00On 7:13 AM on Jul 22 2005 , Lance wrote:LF: To par...On 7:13 AM on Jul 22 2005 , Lance wrote:<BR/><BR/>LF: To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology. <BR/><BR/>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.<BR/><BR/>Regards,<BR/><BR/>Bhupinder Singh AnandAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122133010510805722005-07-23T10:36:00.000-05:002005-07-23T10:36:00.000-05:00On Fri Jul 22, 02:02:03 PM CDT, Gasarch wrote:G: S...On Fri Jul 22, 02:02:03 PM CDT, Gasarch wrote:<BR/><BR/>G: Soare has succeeded in getting people to call it "Computability Theory'' instead of "Recursion Theory''. I doubt this will have much effect.<BR/><BR/>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.<BR/><BR/>G: Connect up with other branches of Math by analyzing foundational questions. <BR/><BR/>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. <BR/><BR/>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'.<BR/><BR/>G: ... Harvey Friedman's REVERSE MATH program about seeing when various types of axioms are needed to prove things. <BR/><BR/>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.<BR/><BR/>G: Connect up to other fields of math by actually helping them to solve some of their problems. <BR/><BR/>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.<BR/><BR/>Regards,<BR/><BR/>Bhupinder Singh AnandAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122058923362795402005-07-22T14:02:00.000-05:002005-07-22T14:02:00.000-05:00Open Problem of Importance: Is there anautomorphis...Open Problem of Importance: Is there an<BR/>automorphism of the Turing Degrees<BR/>(nontrivial).<BR/><BR/>Computability theory was dying, and perhaps<BR/>still is (``its been dying for 20 years'')<BR/>but there are three things going on that<BR/>are trying to revive it. <BR/><BR/>a) Name Change- Soare has succeeded in getting people to call it<BR/>``Computability Theory'' instead of<BR/>``Recursion Theory''. I doubt this will<BR/>have much effect.<BR/><BR/>b) Connect up with other branches of Math<BR/>by analyzing foundational questions.<BR/>Anil Nerode's Recursive math program<BR/>(Computable Math now I guess) looked at<BR/>proofs in OTHER branches of math and<BR/>tried to prove when they can be made<BR/>effective and when they cannot.<BR/>Or find a weaker version of a theorem<BR/>that WAS effective. <BR/>(See HANDBOOK OF RECURSIVE MATHEMATICS.<BR/>The article of most interest to OUR<BR/>community might be mine on <BR/>Recursive Combinatorics.<BR/>on my website www.cs.umd.edu/~gasarch<BR/>or just email me for it)<BR/>ALSO Harvey Friedman's REVERSE MATH<BR/>program about seeing when various types<BR/>of axioms are needed to prove things.<BR/>(This overlaps with Recursive Math<BR/>but is actually different.)<BR/><BR/>c) Connect up to other fields of math by<BR/>actually helping them to solve some of<BR/>their problems. I once gave a talk <BR/>entitled ``Applications of Logic to <BR/>the rest of mathematics'' I had 5.<BR/>That was in 1984. There have been more<BR/>since then, but not alot more.<BR/>I've heard rumors of Algebraic Geometry<BR/>being helped by Model Theory.<BR/>And of Geometry being helped by<BR/>Computability theory. GREAT if it <BR/>actually works, but I am skeptical.<BR/><BR/>MISC: In the STRUCTURES CONFERENCE early days<BR/>there would be an ocasional paper<BR/>like `Theory of the p-m degrees is<BR/>undecidable' That kind of hard<BR/>recursion theory in complexity is gone<BR/>now.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122052862818641762005-07-22T12:21:00.000-05:002005-07-22T12:21:00.000-05:00A major open problem in computability is whether o...A major open problem in computability is whether or not the theory of the rationals is decidable. <BR/><BR/>This seems to be a concrete algorithmic question that complexity theorists and TCS people could get interested in.<BR/><BR/>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...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122050828795310962005-07-22T11:47:00.000-05:002005-07-22T11:47:00.000-05:00I am sure there are many challenging open question...I am sure there are many challenging open questions in computability theory. IMPORTANCE, however, may be in the eye of the beholder :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1122043634969759782005-07-22T09:47:00.000-05:002005-07-22T09:47:00.000-05:00One major difference seems to be that computabilit...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.<BR/><BR/>Is there even a single, imporant open problem left in computability theory?Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.com