No próximo dia 22 de Novembro de 2019, pelas 11h00 na sala FC1 0.29 do Departamento de Matemática, o Professor Juraj Hromkovič irá dar uma palestra intitulada "P vs. NP - What one has to know about this problem".
A palestra é organizada pelo DCC-FCUP e pelo grupo de investigação CMUP e é aberta a todos os interessados.
Short Bio:
Juraj Hromkovič is a Slovak Computer Scientist and Professor at ETH Zürich. His research and teaching interests focus on informatics education, algorithmics for hard problems, complexity theory with special emphasis on the relationship between determinsm, randomness, and nondeterminism. One of his main activities is writing textbooks which make complex recent discoveries and methods accessible for students and practitioners, and so contributing to the speed up of the transformation of new paradigmatic research results into educational folklore.
Title
"P vs. NP - What one has to know about this problem"
Abtract
Mathematics was developed as a strong research instrument with fully verifiable argumentations. We call any consistent and sufficiently powerful formal theory that enables to algorithmically verify for any given text whether it is a proof or not algorithmically verifiable mathematics (AV-mathematics for short). We say that a decision problem L ⊆ Σ∗ is almost everywhere solvable if for all but finitely many inputs x ∈ Σ^* one can prove either “x ∈ L” or “x ∉ L” in AV-mathematics. First, we prove Rice’s theorem for unprovability, claiming that each nontrivial semantic problem about programs is not almost everywhere solvable in AV-mathematics. Using this, we show that there are infinitely many algorithms (programs that are provably algorithms) for which there do not exist proofs that they work in polynomial time or that they do not work in polynomial time. Note that, if P = NP is provable in AV-mathematics, then for each algorithm A it is provable that “A does not solve SATISFIABILITY or A does not work in polynomial time.” Interestingly, we show that there exist algorithms for which it is neither provable that they do not work in polynomial time, nor that they do not solve SATISFIABILITY. Moreover, there is an algorithm solving SATISFIABILITY for which one cannot prove in AV-mathematics that it does not work in polynomial time. Furthermore, we show that P = NP implies the existence of algorithms X for which the true claim “X solves SATISFIABILITY in polynomial time” is not provable in AV-mathematics. Finally, we prove that if P vs. NP is not solvable in AV-mathematics, then P is a proper subset of NP in the world of complexity classes based on algorithms whose behavior and complexity can be analyzed in AV-mathematics. On the other hand, if P = NP is provable, we can construct an algorithm that provably solves SATISFIABILITY almost everywhere in polynomial time.