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
Problem za milion dolarów
Moderator: RedAktorzy
- Cordeliane
- Wynalazca KNS
- Posty: 2630
- Rejestracja: ndz, 16 sie 2009 19:23
Problem za milion dolarów
Light travels faster than sound. That's why some people appear bright until they speak.
- neularger
- Strategos
- Posty: 5230
- Rejestracja: śr, 17 cze 2009 21:27
- Płeć: Mężczyzna
Byłaś bardzo oględna Cordi. Gdyby wykazano, że P=NP to większość kryptologii wylądowałaby na śmietniku.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.
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
Ty, Margoto, niszczysz piękne i oryginalne kreacje stylistyczne, koncepcje cudne językowe.
Jesteś językową demolką. - by Ebola
- No-qanek
- Nexus 6
- Posty: 3098
- Rejestracja: pt, 04 sie 2006 13:03
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:
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.
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:
No, to zależy co uznamy za zastraszające tempo.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.
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..."
- Albiorix
- Niegrzeszny Mag
- Posty: 1768
- Rejestracja: pn, 15 wrz 2008 14:44