Complexity of computation, communication, and search
Project goals
The goal of computational complexity is to find the dividing line between easy, efficiently solvable, tasks and the hard ones. Depending on the nature of the computational task and resources used, this question leads to mathematical problems of varying degrees of difficulty. We will focus on complexity of communication, total search problems, and arithmetic circuit complexity. These areas form a web of interconnected open problems whose solution requires developing new proof methods, and also invites the use of methods from other branches of mathematics, such as combinatorics, graph theory, algebra, or geometry. The problems have related goals, share similar obstacles, and a progress in one will advance the others.
Keywords
computational complexitycommunication complexityTFNParithmetic circuits
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202500001
Main participants
Matematický ústav AV ČR, v. v. i.
Contest type
VS - Public tender
Contract ID
25-16311S
Alternative language
Project name in Czech
Složitost výpočtů, komunikace, a vyhledávání
Annotation in Czech
Cílem výpočetní složitosti je najít hranici mezi snadnými výpočetními úlohami, které lze řešit efektivně, a těmi těžkými. Tato otázka nabývá různých forem v závislosti na povaze úlohy a použitých zdrojů, a vede na matematické problémy různých úrovní obtížnosti. Soustředíme se na složitost komunikace, totálních vyhledávacích problémů, a složitost aritmetických obvodů. Tyto oblasti tvoří propojenou síť otevřených problémů, jejichž řešení vyžaduje rozvinutí nových metod. Nabízí ale také využití metod z jiných oblastí matematiky, jako jsou kombinatorika, teorie grafů, algebra či geometrie. Tyto problémy mají spřízněné cíle, podobné překážky, a řešení jednoho problému znamená pokrok v řešení ostatních.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2025
Realization period - end
Dec 31, 2027
Project status
Z - Beginning multi-year project
Latest support payment
—
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP25-GA0-GA-R
Data delivery date
Feb 27, 2025
Finance
Total approved costs
11,416 thou. CZK
Public financial support
10,939 thou. CZK
Other public sources
477 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
11 416 CZK thou.
Public support
10 939 CZK thou.
95%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2025 - 31. 12. 2027