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 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.
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.
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 (CTU in Prague, Faculty of Information Technologies), Michal Koucký (Charles University, Faculty of Mathematics and Physics), Jan Kybic (CTU in Prague, Faculty of Electrical Engineering), Michal Pěchouček (CTU in Prague, 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 (CTU in Prague, Faculty of Electrical Engineering), and Filip Železný (CTU in Prague, 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.
© 2013-2022, Prague Computer Science Seminar 
This work is licensed under aCreative Commons Attribution 4.0 International License.
