PTCC
Phase transitions and computational complexity
| Coordinatore | JOHANN WOLFGANG GOETHE UNIVERSITAET FRANKFURT AM MAIN
Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie. |
| Nazionalità Coordinatore | Germany [DE] |
| Totale costo | 1˙099˙575 € |
| EC contributo | 1˙099˙575 € |
| Programma | FP7-IDEAS-ERC
Specific programme: "Ideas" implementing the Seventh Framework Programme of the European Community for research, technological development and demonstration activities (2007 to 2013) |
| Code Call | ERC-2011-StG_20101014 |
| Funding Scheme | ERC-SG |
| Anno di inizio | 2011 |
| Periodo (anno-mese-giorno) | 2011-10-01 - 2016-09-30 |
Partecipanti
| # | ||||
|---|---|---|---|---|
| 1 |
THE UNIVERSITY OF WARWICK
Organization address
address: Kirby Corner Road - University House - contact info |
UK (COVENTRY) | beneficiary | 76˙535.06 |
| 2 |
JOHANN WOLFGANG GOETHE UNIVERSITAET FRANKFURT AM MAIN
Organization address
address: GRUNEBURGPLATZ 1 contact info |
DE (FRANKFURT AM MAIN) | hostInstitution | 1˙023˙040.42 |
| 3 |
JOHANN WOLFGANG GOETHE UNIVERSITAET FRANKFURT AM MAIN
Organization address
address: GRUNEBURGPLATZ 1 contact info |
DE (FRANKFURT AM MAIN) | hostInstitution | 1˙023˙040.42 |
Mappa
Word cloud
Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.
Obiettivo del progetto (Objective)
'This is a project in the area of Theoretical Computer Science, particularly discrete algorithms and computational complexity. Many Constraint Satisfaction Problems (`CSPs') such as Boolean satisfiability or graph coloring are well-known to be NP-hard, i.e., the worst-case computation time to solve these problems is exponential in the size of the problem instance. To illuminate the conceptual origins of the computational hardness of these problems, a major research effort over the past 30 years has been the study of Random instances of CSPs. Over the past decade, motivated by problems in statistical mechanics, physicists have developed stunningly detailed hypotheses on the structural and conceptual nature of random CSPs, based on ingenious but highly non-rigorous techniques. These hypotheses have led to a new class of Message Passing Algorithms, as well as to evidence that certain natural types of random CSPs may be computationally intractable. The goal of this project is to study these ideas rigorously and comprehensively from the perspective of the theory of computing.'