For results achieved in the area of computational complexity, prof. RNDr. Pavel Pudlák, DrSc. from the Institute of Mathematics of the CAS has been awarded by the European Research Council (ERC). As the only Czech representative this year, he has won financial support within the prestigious competition “ERC Advanced Grants”, announced for experiences research employees. He succeeded with the project “Feasibility, logic and randomness in computational complexity” and is the fifth laureate of the advanced grant in the Czech Republic after Eduard Feireisl (2012), Josef Michl (2008), Detlef Schröder (2008) and Tomáš Jungwirth (2011).
From a total number of 2,400 applications, the European Research Council supported 284
projects with EUR 660 million. The grant allotted to Prof. Pudlák is for five years and for EUR
1,259,596 (ca CZK 32 million). Prof. Pavel Pudlák is thus the second Czech mathematician in a short
time awarded with the prestigious grant.
Research Work of Prof. Pavel Pudlák
Computational complexity is a discipline, which has a short history and has only recently been
recognised as an important field not only in information science but also in mathematics. This was
certainly contributed to by the fact that the basic questions in this area (such as the famous
problem of “P versus NP”) are mathematical tasks that have resisted all attempts at a resolution
for several decades. The group led by Prof. Pudlák attempts to resolve them using the methods of
mathematical logic. As Prof. Pudlák believes that it is quite possible that the reasons that we
cannot answer these questions are of a fundamental character and therefore it is necessary to study
the logical aspects of these problems. For this reason, he and his co-workers have focused on the
area on the boundary of mathematical logic and the theory of complexity that is called proof
complexity. Whereas computational complexity deals with questions of how difficult it is to
calculate something, proof complexity sets the question of how difficult it is to prove something.
The methods of proof complexity allow us to prove how theoretical results (e.g. the complexity of
some mathematical problems) and also some practical ones – for instance that a certain calculation
task cannot be resolved by a certain type of algorithms. The Prague group along with the group of
Prof. Stephen Cook in Toronto are the two main global centres that deal with this topic.
Prof. Pavel Pudlák on “P versus NP”
Our research is motivated by one important problem called the “P versus NP” problem“. For
laypeople, this problem can be explained as a question of whether there exists some “miraculous
algorithm”. Using this algorithm, many practical tasks could be resolved for which we do not have
sufficiently good algorithms. For instance, production processes, transport timetables, investments
and other tasks could be optimised to the maximum. The algorithm would naturally be very useful
also for the resolution of specific tasks in mathematics and physics. On the other hand, such an
algorithm would have also very negative consequences: it would not be possible safely to use the
coding of secret information. The first person to discover this miraculous algorithm could abuse it
to get into any computer connected to the internet and read the secret data.
This is understandably a somewhat simplified description of the mathematical problem, but under
certain circumstances (if the constants hidden in the formulation of the problem were small) the
described situation could occur. For interest, we will also mention that “P versus NP” is one of
seven mathematical problems, on the resolution of which the Clay Institute has announced a prize of
1 million US dollars.
The majority of scientist who deal with this area of theoretical information science believe
that P is not equal to NP, and hence that the miraculous algorithm does not exist. However, no
method has yet been developed that would allow something like that to be proved. Our group has
focused on an approach based on mathematical logic. We endeavour to seek the connections between
the problems of how to calculate something quickly enough and problems of how to prove something
with a short proof. In other words, we are looking for the connections between calculation
complexity and proof complexity. It will show that these two types of complexity are merely two
various perspective on the general phenomenon of complexity.
Contact:
Prof. RNDr. Pavel Pudlák, DrSc., Institute of Mathematics of the CAS, tel.: +420 222 090 721 begin_of_the_skype_highlighting
+420 222 090 721 FREE end_of_the_skype_highlighting, e-mail:
pudlak@math.cas.cz
+420 222 090 721 FREE end_of_the_skype_highlighting, e-mail:
pudlak@math.cas.czPrepared by: Department of Media Communications of the Head Office of the CAS
1 Oct 2013
