Dr. Clément Dallard - P versus NP: A million-dollar question (and more)

2. Famnitov izlet v matematično vesolje 2021/22

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

Predava: Dr. Clément Dallard, UP FAMNIT in UP IAM

Za številne matematične probleme lahko preverimo, ali je dana rešitev učinkovita. Vendar za nekatere od teh problemov ne poznamo učinkovitega algoritma, s katerim bi lahko določili, ali takšna rešitev obstaja. Ob upoštevanju nekaterih klasičnih problemov smo obravnavali vprašanje P proti NP, njegove teoretične in praktične posledice ter različne pristope k reševanju problemov, za katere ne poznamo učinkovitih algoritmov.
________________________________

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.