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

On 2017-05-25 16:00:00 at KN:E-107 (Zengerova poslucharna)

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.

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.

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