megli

Algorytm rho Pollarda jest probabilistyczny, daje tylko prawdopodobieństwo zwrócenia poprawnego wyniku. Jest wielomianowy, ale trzeba pamiętać, że daje wynik z określonym prawdopodobieństem. Nic nie stoi na przeszkodzie, żeby go zmodyfikować tak aby prawdopodoieństwo było większe, ale kosztem czasu obliczeń. W takim sensie istniały wielomianowe algorytmy do testowania pierwszości na długo przed AKS(i chyba nadal się ich używa) Algorytm Shora jest kwantowy. Chociaż eksperymentalne komputery kwantowe już istnieją, są dosyć ograniczone(przynajmniej oficjalnie). Na chwilę obecną nie da się chyba zastosować algorytmu Shora w praktyce dla większych liczb(jak w kryptografii). Stosowanie RSA pewnie ma wątpliwy sens jeżeli jest inaczej. Może doprecyzuję to co napisałem wcześniej: Nie jest znany deterministyczny wielomianowy algorytm faktoryzacji stosaowalny na klasycznych komputerach. (Deterministyczny - zwracający zawsze poprawną odpowiedź)

Do Jarka Dudy: Znane metody łamania RSA opierają się chyba na faktoryzacji, czyli rozkładzie liczb na czynniki pierwsze. Nie jest znany algorytm wielomianowy do faktoryzacji. Mimo wszystko, rozumiem co miałeś na myśli: Chociaż mamy AKS, czyli wielomianowy algorytm testujący czy liczba jest pierwsza nie okazało się to żadną rewolucją, a nawet do testów pierwszości używa się innych algorytmów. Czyli pewnie masz rację, że samo udowodnienie że P=NP nie było by od razu jakąś rewolucją. Może gdyby udało się: 1. Udowodnić, że P=NP 2. Znaleźć wielomianowy algorytm problemu NPC ograniczony wielomianem niewielkiego stopnia(bardzo wątpliwe) 3. Transformacje problemów NP do problemu NPC z 2 byłyby ograniczone wielomianem niewielkiego stopnia to może rzeczywiście mielibyśmy poważne konsekwencje praktyczne.

Do autora artykułu: Zdanie niepoprawne: "Czas potrzebny do wykonania zadania to P, a czas potrzebny do weryfikacji wyniku to NP" Prawdopodobnie autorowi chodziło o fakt, że dla problemu z klasy P można znaleźć rozwiązanie w czasie wielomianowym(czyli "szybko"), dla problemu z klasy NP weryfikacja poprawności znanego wyniku jest możliwa w czasie wielomianowym(czyli "szybko"). Problem spełnialności SAT jest problemem NP zupełnym, czyli każdy inny problem NP może być przekształcony do problemu SAT w czasie wielomianowym(a zatem jeśli potrafilibyśmy rozwiązać problem SAT w czasie wielomianowym, każdy inny problem NP też byśmy potrafili, wtedy mamy udowodnione, że P=NP) Jeżeli Deolalikar udowodnił, że SAT nie może być rozwiązany w czasie wielomianowym, oznacza to że P!=NP (nie jest możliwe rozwiązanie żadnego problemu NP w czasie wielomianowym, bo po przekształceniu do problemu SAT przeczyłoby to faktowi że SAT nie można rozwiązać w ten sposób - wielomianowo) Do Dudy: Pomijając to co napisał kolega wcześniej(o metodach informatyki teoretycznej), większość proponowanych tu podejść w ogóle nie gwarantuje znalezienia rozwiązania optymalnego(metody gradientowe, algorytmy genetyczne itd.) Często metody te nie mają w ogóle określonego kryterium zakończenia obliczeń, np po pewnym czasie działania algorytmu genetycznego można go zatrzymać i przyjrzeć się wynikowi. Wiemy np że wynik jest lepszy od innych, które znaleźliśmy, ale nie wiemy czy jest to wynik optymalny. Do rmaciej1983: Na pytanie: "Gdyby P=NP, to niby co przewróciłoby się do góry nogami?" Po samym udowodnieniu, że P=NP jeszcze nic. Oznaczałoby to natomiast, że istnieją efektywne(wielomianowe) algorytmy dla wszystkich problemów NP. Istnieją, czyli można je wymyślić, a zatem możemy np łamać szyfry w sensownym czasie. Cała współczesna kryptografia mogłaby upaść(np bankowość elektroniczna). W szczególnośći rozwiązanie dowolnego problemu NPC(NP zupełnego)w czasie wielomianowym spowodowałoby, że znalibyśmy rozwiązania wszystkich problemów NP w czasie wielomianowym. Informatyk