S predavanjem "Po sledeh prstnih odtisov s teorijo grafov" smo zaključili cikel Famnitovih izletov v matematično vesolje 2024/25.
Vabljeni, da se nam pridružite ponovno prihodnje leto.
“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 / ZOOM povezava
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 discussed 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.
