idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
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.)
Information on participating / attending:
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)
Date:
02/17/2010 - 02/20/2010
Event venue:
Alfried Krupp Wissenschaftskolleg Greifswald
Martin-Luther-Straße 14
17489 Greifswald
Mecklenburg-Vorpommern
Germany
Target group:
Scientists and scholars, Students
Email address:
Relevance:
international
Subject areas:
Mathematics
Types of events:
Entry:
01/04/2010
Sender/author:
Marlene Sülberg
Department:
Alfried Krupp Wissenschaftskolleg Greifswald
Event is free:
no
Language of the text:
English
URL of this event: http://idw-online.de/en/event29822
You can combine search terms with and, or and/or not, e.g. Philo not logy.
You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).
Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.
You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).
If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).
