About the project
This project aims at making progress in the study of basic open problems in computational complexity,
such as the P versus NP problem. There are several approaches to these difficult problems,
one of which is proof complexity. In proof complexity we not only study the lengths of proofs in various proof
systems, but also first order theories associated with complexity classes, collectively called bounded arithmetic.
Proving separations between proof systems or theories in bounded arithmetic, however, seems as difficult as separating
the corresponding complexity classes.
Our group has been working in proof complexity for more than two decades and has played an important role in the development
of the field. The novelty of this project is its focus on the role of the following two concepts in proof complexity:
incompleteness and pseudorandomness. The incompleteness phenomenon is well understood in the context of stronger
arithmetical theories, but little is known in bounded arithmetic. As it may be extremely difficult to solve the problems
about incompleteness in the polynomial time domain, one of the approaches we will try is proposing axioms that will
decide these questions. Similarly, pseudorandomness has been intensively researched in computational complexity, but
its role in proof complexity still needs more research. More...