The fundamental goal of this area is to understand the limits of computability (that is analysing which problems can be solved on nowadays and future computers in principle) and effective computability (that is understanding the class of problems which can be solved quickly and with restricted resources) where the most famous open problem is the P = NP-problem, listed on top of the collection of seven Clay Prize problems. Logic provides a multifarious toolbox of techniques to analyse questions like this, some of which promise to provide deep insights in the structure of limit of computation. In our workshop, we shall focus on the following aspects: logical descriptions of complexity (e.g., descriptive complexity, bounded arithmetic), complexity classes of abstract, algebraic and infinite structures, barriers in proving complexity results, and Kolmogorov complexity and randomness. Descriptive complexity and bounded arithmetic are two complementary approaches to describe computational complexity in logical terms. The former is focussed on decision problems, while the latter is more concerned with search problems. Both environments render questions about complexity classes in a natural way, leading to important open problems in their areas (e.g. finding logics to capture certain complexity classes, or the separation problem for bounded arithmetic.)
Hinweise zur Teilnahme:
Conference chair:
Dr. Christine Gaßner (University of Greifswald)
Chair of the Programme Committee:
Dr. Arnold Beckmann (University of Swansea)
Conference fee:
120,- EUR (early registration, until January 15)
150,- EUR (late registration)
Termin:
17.02.2010 - 20.02.2010
Veranstaltungsort:
Alfried Krupp Wissenschaftskolleg Greifswald
Martin-Luther-Straße 14
17489 Greifswald
Mecklenburg-Vorpommern
Deutschland
Zielgruppe:
Studierende, Wissenschaftler
E-Mail-Adresse:
Relevanz:
international
Sachgebiete:
Mathematik
Arten:
Eintrag:
04.01.2010
Absender:
Marlene Sülberg
Abteilung:
Alfried Krupp Wissenschaftskolleg Greifswald
Veranstaltung ist kostenlos:
nein
Textsprache:
Englisch
URL dieser Veranstaltung: http://idw-online.de/de/event29822
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).