Grant: Discovery Grants Program - Individual

What does it mean that a problem has high complexity? Most often by complexity of a problem we mean its computational complexity, that is, the amount of resources needed by the best algorithm solving the problem. The main problems in complexity theory remain unsolved. The celebrated P vs. NP problem, asking whether every problem with an easily verifiable solution can be solved in short time, is listed by the Clay Institute as one of the seven most important problems in mathematics of the 21st century. Complexity theory also deals with other notions of complexity. One of them is the complexity of expressing problems. This is important in database theory; where we want to know which query languages for databases are expressive enough to allow us to ask something non-trivial, and yet computationally are easy enough so that obtaining the answer takes reasonable time. Another notion is the complexity of reasoning. Given a theorem, how complex are the concepts needed to prove it? How long is the shortest possible proof? Can this theorem be proved by an automated proof system? This suggests the following question: if a theorem is expressible with simple concepts, is it easy to prove? In general, even theorems simple to state can have very difficult proofs; Fermat's last theorem is such an example. But is this always the case? The goal of my research is to explore various aspects in which complexity arises and the relationships among them, concentrating on machine-independent types of complexity. As a short-term goal, I plan to study the complexity of describing and reasoning with random-like objects, which are used in proofs of several recent major results in complexity theory.