MINICOMPLEXITY
COMPUTATIONAL COMPLEXITY MEETS AUTOMATA THEORY
| Coordinatore | UNIVERSITE PARIS DIDEROT - PARIS 7
Organization address
address: RUE THOMAS MANN 5 contact info |
| Nazionalità Coordinatore | France [FR] |
| Totale costo | 216˙030 € |
| EC contributo | 216˙030 € |
| Programma | FP7-PEOPLE
Specific programme "People" implementing the Seventh Framework Programme of the European Community for research, technological development and demonstration activities (2007 to 2013) |
| Code Call | FP7-PEOPLE-2009-IEF |
| Funding Scheme | MC-IEF |
| Anno di inizio | 2010 |
| Periodo (anno-mese-giorno) | 2010-09-01 - 2012-08-31 |
Partecipanti
| # | ||||
|---|---|---|---|---|
| 1 |
UNIVERSITE PARIS DIDEROT - PARIS 7
Organization address
address: RUE THOMAS MANN 5 contact info |
FR (PARIS) | coordinator | 216˙030.40 |
Mappa
Word cloud
Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.
Obiettivo del progetto (Objective)
'Computational Complexity classifies computational problems according to difficulty. Although a rich map of time complexity classes has already been developed (P, EXP, EEXP, ...; NP, Delta2P, Sigma2P, Pi2P, ..., PH, AP; ZPP, RP, BPP, PP; IP; BQP; etc.), many fundamental questions about them remain wide open. The most famous one is P vs NP. In 1978, Sakoda and Sipser proposed a 'miniature version' of P vs NP, whose answer could yield insight into P vs NP itself. They asked whether nondeterminism is essential for two-way finite automata (2FA) and size---as opposed to Turing machines (TM) and time. The question is called 2D vs 2N, where 2D and 2N are 2FA-size analogs of P and NP. The objective of this project is to extend the Sakoda-Sipser miniaturization beyond P vs NP and study the 2FA-size analogs of all major time complexity classes. Specifically: 1. To define the 2FA of each mode (deterministic, alternating, probabilistic, interactive, quantum), in a way that convincingly models general 2FA computations and retains connections to TM complexity. To produce a map of robust 2FA-size complexity classes. 2. To update this map with all inclusions/separations from known results of 2FA-size complexity and all straightforward inclusions/separations from ideas of TM complexity. 3. To enrich this map with new types of reductions, new complete problems, new high-level advances, and new inclusions/separations proved by novel algorithmic/lower bound methods. A new field of research will be born, at the intersection of Computational Complexity and Automata Theory. The fellowship will allow the applicant to pursue this research program at a prestigious laboratory, interacting with experts from both Computational Complexity and Automata Theory. It will critically enhance his scientific and professional capacity, diversify expertise at the host laboratory, and significantly increase the attractiveness of the European Research Area.'