Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije

Vabljeni na naslednje predavanje!

Sreda, 24. november 2021,
ob 18.00

Velika predavalnica 3, UP FAMNIT ali preko videokonferenčnega orodja ZOOM

“Cikel poljudnih predavanj o matematiki in njeni vlogi v sodobnem svetu”

P versus NP: A million-dollar question (and more)

natisni

Sreda, 24. november 2021, ob 18.00, Velika predavalnica 3, UP FAMNIT
P versus NP: A million-dollar question (and more)
Dr. Clément Dallard, UP FAMNIT in UP IAM

For many mathematical problems we can check if a given solution is valid efficiently. However, for some of those problems we do not know an efficient algorithm to decide whether such a solution exists. Here lies the P versus NP question, which asks if all those problems admit efficient algorithms or if some problems are intrinsically harder than others. Considering some classical problems with real-life applications, we will discuss the P versus NP question, its theoretical and practical implications, and the various approaches to solve problems for which we do not know efficient algorithms.