Traveling Salesman - kinowy film o konsekwencjach dowodu P = NP
W czerwcu premierę będzie miała ciekawie zapowiadająca się produkcja, na oko trochę w stylu Primer, o tym jakie konsekwencje miałoby udowodnienie, że tożsame są klasy problemów, dla których relatywnie szybko da się znaleźć rozwiązanie i tych, dla których można je relatywnie szybko sprawdzić.
Ardai z- #
- #
- #
- #
- #
- #
- #
- #
- 9
Komentarze (9)
najlepsze
Nie chodzi o szybkie znalezienie rozwiązania dla jakiejś skończonej liczby instancji problemu NP-trudnego, tylko o udowodnienie że istnieje algorytm który rozwiązuje WSZYSTKIE instancje tego problemu (oraz jednocześnie wszystkich innych problemów NP-trudnych) w czasie wielomianowym.
Są to algorytmy, które relatywnie szybko się wykonują, w czasie osiągalnym dla komputerów. Owszem, są prostsze np. zależne od log n, ale są też zależne od 2^n, n! czy n^n.
W tym artykule na wiki jest dobry przykład: Czy jakikolwiek podzbiór zadanego zbioru (np. {-2,6,-3,72,10,-11}) sumuje się do