Problem za milion dolarów

czyli udowodnione lub nie zjawiska, względnie cuda-niewida oraz inne przejawy aktywności obcych

Moderator: RedAktorzy

ODPOWIEDZ
Awatar użytkownika
Cordeliane
Wynalazca KNS
Posty: 2630
Rejestracja: ndz, 16 sie 2009 19:23

Problem za milion dolarów

Post autor: Cordeliane »

Stało się coś ważnego w dziedzinie matematyki/informatyki: w piątek, szóstego sierpnia, Vinay Deolalikar ogłosił pracę, w której twierdzi, że obliczeniowa klasa złożoności NP nie jest równa klasie P.

Po ludzku:
- P to zbiór problemów, dla których można znaleźć rozwiązania w czasie wielomianowym;
- NP to zbiór problemów, dla których można w czasie wielomianowym zweryfikować, czy dane odgórnie rozwiązanie jest poprawne;
- czas wielomianowy oznacza, że algorytm działa w czasie, który da się określić funkcją wielomianową, gdzie zmienną jest rozmiar wejścia (na przykład liczba elementów zbioru, który trzeba posortować). Algorytmy o złożoności wielomianowej są cenne, ponieważ czas ich wykonania dla dużych zbiorów danych nie wzrasta w zastraszającym tempie, w odróżnieniu na przykład od złożoności wykładniczej.
W sposób naturalny P zawiera się w NP (jeśli możemy łatwo sami znaleźć rozwiązanie, to tym bardziej łatwo możemy sprawdzić czy dostarczone rozwiązanie jest prawidłowe), natomiast kwestia zawierania w drugą stronę - a zatem tożsamości klas - dotychczas pozostawała nierozstrzygnięta i stanowiła jeden z siedmiu problemów milenijnych. Listę takich problemów, istotnych dla nauki, ogłoszono w 2000 roku, i za rozwiązanie każdego z nich wyznaczono milion dolarów nagrody (jeden - Hipoteza Poincarégo - został już rozstrzygnięty w 2003 przez Perelmana).

Donioślejsze skutki miałoby dowiedzenie, że P=NP (choć nawet intuicyjnie takie rozwiązanie jest mało prawdopodobne) - oznaczałoby to na przykład, że pewne metody szyfrowania danych nadają się do kosza, ponieważ ktoś może w końcu odkryć algorytm, który je łamie w czasie wielomianowym, zatem nie są bezpieczne.
Wykazanie braku tożsamości powinno natomiast pozwolić udowodnić w formalny sposób, że pewne popularne problemy nie mają prostych rozwiązań, i naukowcy zamiast szukać takowych powinni zająć się czymś bardziej sensownym ;)
Teraz mamy etap dyskusji i szukania dziur w ogłoszonym dowodzie. Dla zainteresowanych pełna praca dostępna jest tutaj:
http://www.scribd.com/doc/35539144/pnp12pt
Light travels faster than sound. That's why some people appear bright until they speak.

Awatar użytkownika
neularger
Strategos
Posty: 5230
Rejestracja: śr, 17 cze 2009 21:27
Płeć: Mężczyzna

Post autor: neularger »

Cordi pisze:Donioślejsze skutki miałoby dowiedzenie, że P=NP (choć nawet intuicyjnie takie rozwiązanie jest mało prawdopodobne) - oznaczałoby to na przykład, że pewne metody szyfrowania danych nadają się do kosza, ponieważ ktoś może w końcu odkryć algorytm, który je łamie w czasie wielomianowym, zatem nie są bezpieczne.
Byłaś bardzo oględna Cordi. Gdyby wykazano, że P=NP to większość kryptologii wylądowałaby na śmietniku.
A ja bym zlikwidował konto w banku. Pieniążki na rączkę poproszę. :)
Langłydż... Czyli nie dość, że połowa wolnych zasobów neuronów będzie się starała zrozumieć co właśnie przeczytano, to druga będzie pracowała nad translacją. ;)

e. poprawa zrozumiałości
You can do anything you like... but you must never be rude. Rude is being weak.
Ty, Margoto, niszczysz piękne i oryginalne kreacje stylistyczne, koncepcje cudne językowe.
Jesteś językową demolką.
- by Ebola ;)

Awatar użytkownika
No-qanek
Nexus 6
Posty: 3098
Rejestracja: pt, 04 sie 2006 13:03

Post autor: No-qanek »

Jeśli ten dowód zostanie zweryfikowane i potwierdzony - to wielkie WOW!

W ogóle ostatnio przeżywam prawdziwą eksplozję dowodów na stare, potężne problemy matematyczne - WTF udowodnione przez Wilsona, twierdzenie o czterech barwach, ostatnio Perelman dowiódł hipotezy Poincarego, a teraz rozwiązany ma być stary problem "P=NP?"
Hipotezo Goldbacha - drżyj!

Niedługo mogą się chyba kończyć istotne problemy (wiem, wiem - różnych zagadnień związanych z subtelnymi rachunkami różniczkowymi jeszcze od cholery zostało) - a to może skutkować powstawaniem zupełnie nowych dziedzin matematyki.

Chyba zrobi się ciekawie. A dowód sobie przejrzę - pewnie po 5 stronach utknę ;-)

EDIT:
Algorytmy o złożoności wielomianowej są cenne, ponieważ czas ich wykonania dla dużych zbiorów danych nie wzrasta w zastraszającym tempie, w odróżnieniu na przykład od złożoności wykładniczej.
No, to zależy co uznamy za zastraszające tempo.
Są znane algorytmy na (zdaje się) problem sieci minimalnej, które jednakże rosną w tempie n^7 (gdzie n to ilość miast) - i to jest wystarczająco zastraszające tempo, by udupiać superkomputery.
"Polski musi mieć inny sufiks derywacyjny na każdą okazję, zawsze wraca z centrum handlowego z całym naręczem, a potem zapomina i tęchnie to w szafach..."

Awatar użytkownika
Albiorix
Niegrzeszny Mag
Posty: 1768
Rejestracja: pn, 15 wrz 2008 14:44

Post autor: Albiorix »

Kurcze, pamiętam tylko że kwestie klasy algorytmów liczyło się łatwo a dowodziło ciężko. Gdybym miał zrozumieć ten dowód, musiałbym sobie sprawić straszliwie gigantyczną powtórkę :(
nie rozumiem was, jestem nieradioaktywny i nie może mnie zniszczyć ochrona wybrzeża.

ODPOWIEDZ