Prof. Juraj Hromkovic (ETH Zurich) presents Why P vs. NP is so hard?

Prague Computer Science Seminar:

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.