|
Suche |
|
|
|
|
|
|
IT-Messekalender und Veranstaltungen
|
|
« zurück
Event-Ansicht
Mittwoch, 17. Feb. 2010
Logical Approaches to Barriers in Computing and Complexity
Computability theory and complexity theory have their origins in logic. Famous names such as Gödel, Turing, Cook, and Kolmogorov connect these areas of computer science to foundations of mathematics.
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.)
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)
Bitte vergeben Sie für diesen Event eine Note
zwischen +3 (empfehlenswert) und -3 (nicht empfehlenswert)
|
|
Aktuelle Auswertung:
Gesamtbewertung (Alle Punkte):
Plus: , Neutral: , Minus:
|
|
Benutzer-Beiträge
Neue Einträge können Sie - als angemeldeter - User erstellen.
[Anmelden - klick hier]
|
|
|
|
