FEALORA

"Feasibility, logic and randomness in computational complexity"

Coordinatore	MATEMATICKY USTAV AV CR V.V.I.    more 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

#	participant	country	role	EC contrib. [€]
1	MATEMATICKY USTAV AV CR V.V.I.  Organization address address: ZITNA 609/25 city: PRAHA 1 postcode: 115 67 contact info Titolo: Dr. Nome: Ji?í Cognome: Rákosník Email: send email Telefono: +420 222 090 762 Fax: +420 222 090 701	CZ (PRAHA 1)	hostInstitution	1˙259˙596.00
2	MATEMATICKY USTAV AV CR V.V.I.  Organization address address: ZITNA 609/25 city: PRAHA 1 postcode: 115 67 contact info Titolo: Prof. Nome: Pavel Cognome: Pudlák Email: send email Telefono: +420 222 090 721 Fax: +420 222 090 701	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.'