A structural complexity approach to propositional proof systems
FP4 — Training and Mobility of Researchers
- Duration
- 1996-02-01 → 1999-01-31
- EU contribution
- —
- Participants
- 2
- Scheme
- RGI
Lines connect the coordinator with its partners. CORDIS does not always give exact coordinates for projects before 2014. These points are placed at city or country level.
Project objective
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.
Original text from CORDIS.
Participants
Links
Data: CORDIS, © European Union