FEALORA
"Feasibility, logic and randomness in computational complexity"
| Coordinatore | MATEMATICKY USTAV AV CR V.V.I.
Spiacenti, non ci sono informazioni su questo coordinatore. Contattare Fabio per maggiori infomrazioni, grazie. |
| Nazionalità Coordinatore | Czech Republic [CZ] |
| Totale costo | 1˙259˙596 € |
| EC contributo | 1˙259˙596 € |
| 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-2013-ADG |
| Funding Scheme | ERC-AG |
| Anno di inizio | 2014 |
| Periodo (anno-mese-giorno) | 2014-01-01 - 2018-12-31 |
Partecipanti
| # | ||||
|---|---|---|---|---|
| 1 |
MATEMATICKY USTAV AV CR V.V.I.
Organization address
address: ZITNA 609/25 contact info |
CZ (PRAHA 1) | hostInstitution | 1˙259˙596.00 |
| 2 |
MATEMATICKY USTAV AV CR V.V.I.
Organization address
address: ZITNA 609/25 contact info |
CZ (PRAHA 1) | hostInstitution | 1˙259˙596.00 |
Mappa
Word cloud
Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.
Obiettivo del progetto (Objective)
'We will study fundamental problems in complexity theory using means developed in logic, specifically, in the filed of proof complexity. Since these problems seem extremely difficult and little progress has been achieved in solving them, we will prove results that will explain why they are so difficult and in which direction theory should be developed.
Our aim is to develop a system of conjectures based on the concepts of feasible incompleteness and pseudorandomness. Feasible incompleteness refers to conjectures about unprovability of statements concerning low complexity computations and about lengths of proofs of finite consistency statements. Essentially, they say that incompleteness in the finite domain behaves in a similar way as in the infinite. Several conjectures of this kind have been already stated. They have strong consequences concerning separation of complexity classes, but only a few special cases have been proved. We want to develop a unified system which will also include conjectures connecting feasible incompleteness with pseudorandomness. A major part of our work will concern proving special cases and relativized versions of these conjectures in order to provide evidence for their truth. We believe that the essence of the fundamental problems in complexity theory is logical, and thus developing theory in the way described above will eventually lead to their solution.'