CTU Events

29. PIS Prof. Hromkovič: Why P vs. NP is so hard?

25 May 2017   16:00-18:00

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č 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 will take place 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 will consist of a one-hour lecture followed by a discussion. The lecture should be 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 will be in English.
The seminar framework was laid out by the preparatory committee consisting of Michal Chytil (Czech Academy of Sciences, Computer Science Institute), Pavel Kordík (Czech Tech. Univ., Faculty of Information Technologies), 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), 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.

Place

KN:E-107 (Zengerova posluchárna, budova E, FEL, Karlovo nám. 13, Praha 2)

Organizer

Přípravný výbor PIS

Contact person

Veronika Šínová, sinova@fel.cvut.cz, 224 35 7667

More information

http://praguecomputerscience.cz/index.php?l=en&p=29