2014
2015
2016
2017

The twenty-ninth meeting of the Prague computer science seminar

Juraj Hromkovič

Why P vs. NP is so hard?

We are missing methods for proving nontrivial lower bounds on the computational complexity of concrete problems, and thus, we are missing approaches enabling to solve fundamental problems of complexity theory such as P vs. NP, DLOG vs. NLOG etc.

May 25, 2017

4:00pm

Auditorium E-107, FEL CTU
Karlovo nám. 13, Praha 2
Show on the map

Lecture annotation

We are missing methods for proving nontrivial lower bounds on the computational complexity of concrete problems, and thus, we are missing approaches enabling to solve fundamental problems of complexity theory such as P vs. NP, DLOG vs. NLOG etc. We view mathematics as a research instrument and as a language with an unambiguous interpretation of each statement and verifiable argumentation. We call a formal system an algorithmically verifiable mathematics (AV-mathematics) if it is consistent and there exists an algorithm that decides for a given text whether it is a proof or not.

Then we show that there are infinitely many algorithms for which there is neither a proof that they work in polynomial time or not, nor proofs that they solve or do not solve the satisfiability problem. This motivates us to introduce a new version of P as the set of decision problems solved by algorithms such that it is provable that they work in polynomial time. Then we show that if P = NP, then there is a constructive proof of this fact.

Lecturer

Juraj Hromkovič

Juraj Hromkovič is a full professor at ETH Zurich since 2004, where he founded the ETH Centre for Computer Science Education of which he has been Chair until present. His research interests include algorithmics for hard problems, complexity theory, online algorithms, automata theory and computer science education. He published around 200 scientific papers and 15 books. Prior to his current position, he was a professor at Comenius University (1989), University of Paderborn (1989 - 1994), CAU Kiel (1994 - 1997), and RWTH Aachen (1997- 2003). In 2001 he was elected a member of the Slovak Academic Society, in 2008 a member of the Learned Society of the Slovak Academy of Sciences, and in 2010 a member of the Academia Europaea. In 2017 he was awarded "Pribina Cross of the first class" by the President of the Slovak Republic.

ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR

The seminar takes place usually on the 4th Thursday of each month at 4:00pm (except June, July, August and December) alternately in the buildings of Faculty of Electrical Engineering, Czech Technical University, Karlovo nám. 13, Praha 2 and Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, Praha 1.

Its program consists of a one-hour lecture followed by a discussion. The lecture is based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures are in English.

The seminar is organized by the organizational committee consisting of Roman Barták (Charles University, Faculty of Mathematics and Physics), Jaroslav Hlinka (Czech Academy of Sciences, Computer Science Institute), Michal Chytil, Pavel Kordík (Czech Tech. Univ., Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (Czech Tech. Univ., Faculty of Electrical Engineering), Michal Pěchouček (Czech Tech. Univ., Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences, Institute of Information Theory and Automation), Tomáš Werner (Czech Tech. Univ., Faculty of Electrical Engineering), and Filip Železný (Czech Tech. Univ., Faculty of Electrical Engineering)

The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.

Supporters

Contact