Zajęcia 10: Problemy 3SUM-trudne

Problem 3SUM

Problem 3SUM jest sformułowany następująco: Dany jest zbiór S złożony z n liczb całkowitych. Czy istnieją elementy a,b,c ∈ S, takie że a+b+c=0? Zadanie domowe polega na rozwiązaniu tego problemu w czasie O(n²). Okazuje się, że nie jest znane żadne rozwiązanie tego problemu w czasie istotnie lepszym niż O(n²). Na zajęciach pokażemy, jak z tego faktu wyprowadzić (potencjalną) trudność rozwiązania wielu problemów geometrycznych w czasie o(n²). Więcej informacji w artykule z Delty o 3SUM-trudności.

Zadanie domowe

Zadanie domowe: implementacja rozwiązania zadania 3SUM na ASD-SIO.