Search



Ročenka AV ČR 2014

Academic bulletin / Živa

abicko- ziva

Movies from world of sciences

videoprezentace-blok-bgd.jpg

BIOCEV

A Czech mathematician has acquired a prestigious European grant

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

Prepared by: Department of Media Communications of the Head Office of the CAS

 

1 Oct 2013