H2020Индивидуална стипендия2015–2018

ReACT · A Realizability Approach to Complexity Theory

„Хоризонт 2020“ — Действия „Мария Склодовска-Кюри“

Период: 2015-11-01 → 2018-03-27
Финансиране от ЕС: 212 195 €
Участници: 1
Схема: MSCA-IF-EF-ST

Линиите свързват координатора с партньорите.

Накратко на български

Теорията на сложността изследва ресурсите, необходими за изпълнение на програма, например колко памет или време изисква един алгоритъм. Новият математически подход помага за сравнение между различни видове изчисления, като последователните и квантовите, и анализиране на отворени проблеми в областта.

Този кратък обзор е генериран от изкуствен интелект

Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.

Резултати накратко

A Realizability Approach to Complexity Theory

Complexity theory lies at the intersection between mathematics and computer science, and studies the amount of resources needed to run a specific program (complexity of an algorithm) or solve a particular problem (complexity of a problem). The ReACT project aimed at building on recent work in realizability models for linear logic to provide new characterizations of existing complexity classes, in particular L (logarith- mic space) and P (polynomial time). The final goal was that these characterizations would enable researchers to attack long-standing open problems in complexity theory by using mathematical techniques, tools and invariants from the fields of operators algebras and dynamical systems. The complexity-through-realizability techniques developed by the ReACT project were expected to provide a unified framework for studying many computational paradigms and their associated computational complexity theory grounded on well-studied mathematical concepts. This would allow comparison of complexity classes defined from different computational paradigms (e.g. sequential and quantum computation), as well as establish a theory of complexity for computational paradigms currently lacking such a theory (e.g. concurrent processes). The ReACT project had two objectives. The first objective aimed at establishing this new approach to complexity as an emerging and promising field of study on the basis that it captures, generalizes and extends the techniques developed by previous approaches such as Implicit Computational Compelxity (ICC). The second objective was more exploratory and its goal was to investigate how the new methods and techniques derived from the mathematical foundations of Interaction Graphs models can be used to address open problems in complexity, namely problems related to the question of classifying complexity classes, i.e. deciding if two classes are equal or not.

Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз

Цел на проекта

Complexity theory concerns fundamental questions on the mathematics of computer science about the amount of resources needed to run programs or solve problems. The ReACT project will build on recent work in realizability models for linear logic to provide new characterizations of existing complexity classes. The end goal is to enable researchers to attack long-standing open problems in complexity theory by using mathematical techniques, tools and invariants from operators algebras and dynamical systems.The ""complexity-through-realizability"" techniques developed by the ReACT project will provide a unified framework for studying many computational paradigms and their associated computational complexity theory grounded on well-studied mathematical concepts. This will allow for comparison of complexity classes defined from different computational paradigms (e.g. sequential and quantum computation), as well as establish a theory of complexity for computational paradigms lacking such (e.g. concurrent processes).The ""complexity-through-realizability"" approach stems from established logical-based approaches of complexity theory and inherits their strengths. It furthermore improves crucially over them as it builds upon state-of-the-art theoretical results on realizability models for linear logic using well-studied mathematical concepts from operators algebras and dynamical systems. As a consequence, it opens the way to the use against the open problems of the discipline the many techniques, tools and invariants that were developed in these mathematical disciplines.The ReACT project has two objectives. The first objective aims at establishing this new approach to complexity as an emerging and promising field of study which generalizes and extends previous techniques. The second objective is to investigate investigating how the mathematical methods and techniques derived from of our approach can be used to attack long-standing open problems in complexity theory.""

Оригинален текст от CORDIS (на английски).

Участници

KOBENHAVNS UNIVERSITET · KOBENHAVNКоординаторДания