\n

Compu tability theory and complexity theory have their o rigins\n in logic. Famous names such as Goe del, Turing, Cook, and\n Kolmogorov connect these areas of computer science to foundations\n of mathematics. The fundamental goal of thi s area is to understand\n the limits of com putability (that is analysing which problems can\n be solved on nowadays and future computers in principle) and\n effective computabilit y (that is understanding the class of\n pro blems which can be solved quickly and with restric ted\n resources) where the most famous open problem is the P=NP-problem.\n Logic provi des a multifarious toolbox of techniques to analys e\n questions like this, some of which prom ise to provide a deep\n insight in the stru cture of limit of computation.\n

\nIn our workshop, we shall focus on the followin g aspects: logical\n descriptions of comple xity (e.g., descriptive complexity, bounded\n arithmetic), complexity classes of abstract, al gebraic and\n infinite structures, barriers in proving complexity results, and\n Kolmo gorov complexity and randomness.\n

\nSome of these aspects are particularly timely : recently, research\n in these areas becam e more intense. Part of this is the new\n c onference series CiE (run by the Association for C omputability\n in Europe) whose range of in terests includes those of our\n workshop, c reating an important focus on the emerging topics of\n the field. This workshop is intended a s a research-oriented\n follow-up to the Ci E conferences, allowing researchers ample time\n for discussions and joint work.\n

\ n \n \nFor more information, see\ n http://www.cs.swan.ac.uk /greifswald2010/\n

\n\
n

URL:/NewsandEvents/Archives/2010/newsitem/2837/17-
20-February-2010-Workshop-on-Logical-Approaches-to
-Barriers-in-Computing-and-Complexity-Greifswald-G
ermany
END:VEVENT
END:VCALENDAR
The Programme Committee cordially invite s all researchers in the\n area of the work shop to submit their extended abstracts\n ( in PDF-format, at most 4 pages) for presentation a t the workshop.\n Submission deadline is 15 October 2009.\n

\n