A structural complexity approach to propositional proof systems
4РП — Обучение и мобилност на изследователи
- Период
- 1996-02-01 → 1999-01-31
- Финансиране от ЕС
- —
- Участници
- 2
- Схема
- RGI
Линиите свързват координатора с партньорите. За проекти отпреди 2014 г. CORDIS не винаги дава точни координати. Тези точки са на ниво град или държава.
Накратко на български
Логическите системи за доказване се анализират чрез структурна сложност, например чрез използване на сложността на Колмогоров. Това помага да се разберат границите на тези системи и връзката им с изчислителната сложност на електронните схеми.
Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.
Цел на проекта
The purpose of the project is to give a new approach, based on structural complexity techniques, to solve problems arising in field of complexity of proofs in propositional proof systems. In particular we intend to: -improve the proofs of existing lower bounds for known proof systems using new complexity techniques (like Kolmogorov Complexity); -apply results about relationship between complexity classes to compare different proof systems; -establish the exact correspondence between proof system complexity and circuit complexity; -prove new lower bounds applying both new combinatorial techniques from Kolmogorov complexity and probabilistic arguments. We intend to develop the project during the four years PhD degree requires.
Оригинален текст от CORDIS (на английски).
Участници
Връзки
Данни: CORDIS, © Европейски съюз