Ján Pich
Department of Computer Science
University of Oxford
jan.pich@cs.ox.ac.uk
I am a Marie Curie research fellow at the Algorithms and Complexity Theory Group.
Research interests: Mathematical Logic and Complexity Theory. In particular, Proof Complexity.
How hard is it to separate P and NP?
The P versus NP problem is one of the central questions in the theory of computing. It has been formally introduced already 50 years ago. However, despite enormous efforts
invested into the problem during the decades, its solution appears to be nowhere near. What is behind its notorious difficulty?
Can we automate creative and challenging tasks such as proving mathematical theorems or designing learning algorithms? Such questions can be formalized in the language of
computational complexity theory and constitute some of the most fundamental scientific problems of our times. A famous obstacle in the center of these pursuits known as the
P versus NP problem asks, intuitively, whether it is possible to solve efficiently (in P-time) all problems whose solutions can be efficiently verified (NP-problems).
Unfortunately, since the early days of complexity theory it became clear that some of its main problems are not going to be easy to resolve. Already in the 70's, a discovery of
the relativization barrier clarified why proof methods based purely on diagonalizing arguments, otherwise successfully applied in addressing several related questions, cannot
succeed in separating P and NP. Researchers then turned their attention to more concrete proof methods with a hope of developing non-diagonalizing arguments. An elegant model
of boolean circuits, and proving lower bounds on the complexity of boolean circuits, looked particularly promising for that purpose. This program was met with an initial success
in the 80's with the invention of many complexity lower bounds for restricted classes of circuits. By the end of the 80's it became, however, increasingly more and more evident
that the story is not going to end so fast. These fears were fully materialized in the early 90's when Razborov and Rudich discovered the natural proofs barrier for proving
circuit lower bounds, which symbolically closed another era in our attempts to attack the P versus NP problem.
Razborov, who stood also behind some of the most popular lower bounds of the 80's, had, however, a much more ambitious goal. He wanted to show that circuit lower bounds
present a limit to what is achievable by strong fragments of logical reasoning and postulated several conjectures to this effect in early 00's. One of these conjectures,
in its strongest form implies that strong circuit lower bounds cannot be proved in a theory PV. The theory PV, introduced by Cook, can be interpreted as a fragment of
Peano Arithmetic and formalizes the notion of efficient (P-time) reasoning. Ironically, the progress on proving such unprovability results turned out to suffer from
similar obstacles as those preventing us from solving the P versus NP problem itself - just like we do not understand the power of P-time algorithms, we do not
understand the power of P-time reasoning.
In a recent paper co-authored with Rahul Santhanam, which is going to be presented at the Symposium on Theory of Computing (STOC) 2021, we contributed to this research direction by showing
that very strong complexity lower bounds such as NP being hard on average for co-nondeterministic circuits of subexponential size, which would in particular separate P and NP,
cannot be proved in theories such as PV. The power of these theories can be demonstrated by the fact that many classical theorems from computational complexity are provable in
them, including, for example, the PCP theorem and the circuit lower bounds discovered in the 80's.
We hope that our result will clarify which methods are needed to derive strong complexity separations and eventually help to bring us closer to the actual solution of
problems such as the P versus NP.
Acknowledgement: This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodovska-Curie grant agreement No 890220.