chlapcok 13.08.10, 16:17 To też teoria: P=/=NP N i P= NIP. Odpowiedz Link Zgłoś czytaj wygodnie posty
mkwa Milion dolarów za nierówność 13.08.10, 16:31 Każdy googlający szybko znajdzie na przykład to: michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p≠np/ Krótko: jest *dużo* wątpliwości. Odpowiedz Link Zgłoś
mamula66 Raz w miesiacu 13.08.10, 17:06 Taki dowod pojawia sie srednio raz w miesiacu. Po czym jest obalany, albo ignorowany. ten dowod ma numer 4532 Odpowiedz Link Zgłoś
pioc2 Re: Raz w miesiacu 13.08.10, 20:01 mamula66 napisał: > Taki dowod pojawia sie srednio raz w miesiacu. Ten raczej do takich nie należał, przeczytaj jedną z pierwszych reakcji: rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ Odpowiedz Link Zgłoś
mamula66 Nie interesuja mnie pierwsze reakcje 13.08.10, 21:46 Nie interesuje mnie co pisze wolrldpress. Interesuje mnie co na ten temat mowia specjalisci. A specjalisci poki co owa rewelacje kompletnie olali Odpowiedz Link Zgłoś
pioc2 Re: Nie interesuja mnie pierwsze reakcje 13.08.10, 23:32 mamula66 napisał: > Nie interesuje mnie co pisze wolrldpress. jak podaję linka, to po to, żebyś tam zajrzał. kogo uważasz za 'specjalistę'? Odpowiedz Link Zgłoś
mamula66 Re: Nie interesuja mnie pierwsze reakcje 14.08.10, 00:07 Za specjaliste uwazam srodowisko naukowe. Jest bardzo duza grupa powaznych osob zajmujacaa sie problemem P/NP, i to oni powinni zweryfikowac dowod. Dopiero POTEM nalezy zawiadomic media. Jezeli sie NAJPIERW zawiadamia media, to powstaje podejrzenie o "hucpe". W szczegolnosci luzna dyskusja na webie nie dowodzi niczego Odpowiedz Link Zgłoś
pioc2 Re: Nie interesuja mnie pierwsze reakcje 14.08.10, 07:28 mamula66 napisał: > Za specjaliste uwazam srodowisko naukowe. Jest bardzo duza grupa > powaznych osob zajmujacaa sie problemem P/NP proszę o nazwiska, konkret jakiś > Dopiero POTEM nalezy zawiadomic media. Jezeli > sie NAJPIERW zawiadamia media To znaczy, że wciąż nie zajrzałeś do linka, który podałem powyżej. Jak możemy sensownie dyskutować, jeśli nie interesują ciebie moje argumenty? Odpowiedz Link Zgłoś
jszania jestes niedzisiejszy 17.08.10, 12:50 mamula66 napisał: > Za specjaliste uwazam srodowisko naukowe. Jest bardzo duza grupa > powaznych osob zajmujacaa sie problemem P/NP, i to oni powinni > zweryfikowac dowod. Dopiero POTEM nalezy zawiadomic media. Jezeli > sie NAJPIERW zawiadamia media tak to sie robilo 100 lat temu. uczony dlugo weryfikowal, bo sie bal kompromitacji. w dzisiejszych czasach populatnosc jest wszystkim, a kompromitacja niemal nie istnieje. Odpowiedz Link Zgłoś
neuromancer0 Re: Nie interesuja mnie pierwsze reakcje 13.08.10, 23:36 Hahaha, ale się uśmiałem z tego posta :D Odpowiedz Link Zgłoś
neuromancer0 Re: Nie interesuja mnie pierwsze reakcje 14.08.10, 21:10 Ja mówiłem o Twoim poście :P Odpowiedz Link Zgłoś
syslomm Milion dolarów za nierówność 13.08.10, 23:57 Drobiazg językowy: dowód dotyczy braku równości, a nie nierówności, chociaż między P i NP jest w pewnym sensie nierówność, bo NP zawiera P, ale to jest fakt wynikający z definicji obu klas. Maciej M Sysło Odpowiedz Link Zgłoś
mamula66 Re: Milion dolarów za nierówność 14.08.10, 01:19 Tak na zupelnym marginesie, istnieje konkurencyjny dowod ze P=NP, autorstwa Moustapha Diaby. Twierdzi on ze znalazl algorytm przy pomocy ktorego rozwiazuje Problem Komiwojazera przy pomocy Programowania Liniowego. Jakis rok temu toczyla sie na comp.theory i sci.op-research zazarta dyskusja ktora trwala prawie pol roku. Pewnien mlocy czlowiek (z Polski zreszta) znalazl dwa kontrprzyklady, ktore wedle autora dowodu sa "irrelewant". Wypowiedz Pana Diaby na temat ostatniego dowodu i jego dowodu moza znalezc na sci.op-research (z wczoraj). Mnie sie nei podoba ze najpierw jest wrzawa medialna, a POTEM sprawa weryfikacji dowodu. Afera "cold fusion" nasuwa tu kiepskie paralele. Weryfikacja dowodu Perelmana trwala cos 3 lata, dowodu Twierdzenia Fermata jeszcze dluzej, a w pierwszych wersjach wykryto bledy. Dopiero PO zweryfikowaniu dowodow zaangazowano media. Tutaj wydaje mi sie dokladnie na odwrot. Odpowiedz Link Zgłoś
pioc2 Re: Milion dolarów za nierówność 14.08.10, 07:33 mamula66 napisał: > Mnie sie nei podoba ze najpierw jest wrzawa medialna, a POTEM > sprawa weryfikacji dowodu. taki jest świat w dobie internetu, chcesz walczyć z wiatrakami? > Afera "cold fusion" nasuwa tu kiepskie paralele. złe porównanie, tutaj nie było żadnej konferencji prasowej. Dowiedz się wreszcie, przeczytaj gdzieś (choćby w linku, który podałem), jak to się wszystko zaczęło. Do licha, było dokładnie tak jak z Perelmanem. Facet nie poszedł do prasy, lecz opublikował dowód w internecie i wysłał go też grupie matematyków z branży. Nie zależnie od tego, czy dowód się utrzyma, czy nie - Twoje komentarze są jak kulą w płot. Odpowiedz Link Zgłoś
artur.56 Re: Milion dolarów za nierówność 14.08.10, 21:22 pioc2 napisał: > mamula66 napisał: > > > Mnie sie nei podoba ze najpierw jest wrzawa medialna, a POTEM > > sprawa weryfikacji dowodu. > > taki jest świat w dobie internetu, chcesz walczyć z wiatrakami? > > Taki byl swiat zawsze i takim jest. Ludzie dziela sie na tych co pracuja uczciwie i tych co sie chca bogacic "uczciwie". Odpowiedz Link Zgłoś
bimota Milion dolarów za nierówność 14.08.10, 00:16 A to trzeba udawadniac, ze skoro nie znamy hasla to trudno je odgadnac ?? Odpowiedz Link Zgłoś
stefan4 Czy problem faktoryzacji jest NP-zupełny? 14.08.10, 22:10 Cytat Do tej klasy problemów należy też możliwość łamania współczesnych szyfrów, które chronią dostęp do naszych kont bankowych i kart kredytowych. Dostępu do naszych kont chroni podejrzewana wysoka złożoność problemu faktoryzacji (czyli rozkładu na czynniki) dużych liczb naturalnych. Należy on do klasy NP, więc gdyby P=NP, to ta ochrona by padła. Ale dla bezpieczeństwa tych kont potrzeba więcej, samo P≠NP nie wystarczy. Z tego, że klasa NP\P jest niepusta, nie wynika jeszcze, że problem faktoryzacji do niej należy. Chyba, żeby dowiedziono, że problem faktoryzacji jest dla niej uniwersalny, czyli NP-zupełny, tak jak problem komiwojażera. Kto wie, czy problem faktoryzacji jest NP-zupełny? - Stefan Odpowiedz Link Zgłoś
asteroida2 Re: Czy problem faktoryzacji jest NP-zupełny? 15.08.10, 18:17 > Kto wie, czy problem faktoryzacji jest NP-zupełny? Tego nie wiadomo, ale są silne przesłanki żeby zakładać, że nie jest. Taką przesłanką jest np. istnienie algorytmu kwantowej faktoryzacji. Oznacza to, że problem ma specyficzną strukturę której problemy NP-zupełne nie mają. To jest w ogóle ciekawe, bo istnieje bardzo niewiele problemów które nie mają wielomianowego rozwiązania a nie wiadomo czy są NP-zupełne: en.wikipedia.org/wiki/NP-Intermediate A jeszcze ciekawsze jest, że udowodnienie że jakiś problem nie ma rozwiązania wielomianowego to naprawdę duża sztuka. Na razie nie udowodniono o żadnym problemie (w tym NP-zupełnych), że nie ma rozwiązania w czasie O(n^2). Choć wydawałoby się, że taki problem powinien być prostszy. Odpowiedz Link Zgłoś
alsor Re: Czy problem faktoryzacji jest NP-zupełny? 15.08.10, 20:06 > Tego nie wiadomo, ale są silne przesłanki żeby zakładać, że nie jest. Taką przesłanką jest np. istnienie algorytmu kwantowej faktoryzacji. To normalna rzecz - gdy zwiększysz pamięć, wtedy ta złożoność spada. Przykładowo sortowanie - bez dodatkowej pamięci, czyli in situ: n*ln(n); a gdy masz dużo pamięci, wtedy złożoność: ~ln(n), albo nawet 1. Odpowiedz Link Zgłoś
alsor Re: Czy problem faktoryzacji jest NP-zupełny? 15.08.10, 20:48 > a gdy masz dużo pamięci, wtedy złożoność: ~ln(n), albo nawet 1. źle, minimum rzędu n, czyli przepisanie tablicy... Odpowiedz Link Zgłoś
asteroida2 Re: Czy problem faktoryzacji jest NP-zupełny? 16.08.10, 09:47 > To normalna rzecz - gdy zwiększysz pamięć, wtedy ta złożoność spada. No tak, tylko czemu w takim razie nie ma efektywnych kwantowych algorytmów dla wszystkich problemów NP? Odpowiedz Link Zgłoś
alsor Re: Czy problem faktoryzacji jest NP-zupełny? 16.08.10, 14:39 > No tak, tylko czemu w takim razie nie ma efektywnych kwantowych algorytmów dla wszystkich problemów NP? Bo to pewnie nie dział. W przypadku QM ta pamięć ma wynikać z własności tego splątania - coś tam się powiela, a że są splątania, więc to idzie jakoś lawinowo. No ale przecież splątanie kwantowe jest tylko w QM - tym modelu matematycznym. W praktyce są tylko parametry - spin, faza, energia, kierunek, oraz zwyczaje korelacje pomiędzy nimi... Odpowiedz Link Zgłoś
stefan4 Re: Czy problem faktoryzacji jest NP-zupełny? 16.08.10, 18:34 alsor: > Przykładowo sortowanie - > bez dodatkowej pamięci, czyli in situ: n*ln(n); > a gdy masz dużo pamięci, wtedy złożoność: ~ln(n), albo nawet 1. Z dowolną ilością pamięci sortować przez porównania z jednym procesorem nie da się szybciej niż proporcjonalnie do n·log(n). Zwiększenie liczby procesorów do (proporcjonalnie) n^2 pozwala skrócić ten czas do log(n) Odpowiedz Link Zgłoś
alsor Re: Czy problem faktoryzacji jest NP-zupełny? 16.08.10, 18:50 > Z dowolną ilością pamięci sortować przez porównania z jednym > procesorem nie da się szybciej niż proporcjonalnie do n·log(n). Nie trzeba porównywać kilka razy jednego z innymi: przeliczasz klucze na liczby (robisz to raz dla każdego, czyli n operacji), a potem już tylko indeksujesz... sztuczka z pamięcią asocjacyjną. W innych problemach też da się zredukować złożoność, nawet NP - np. komiwojażer. Tyle że tu zapotrzebowanie na pamięci rośnie wykładniczo, czyli wchodzą w grę jedynie hardwerowe rozwiązania. Odpowiedz Link Zgłoś
stefan4 Re: Czy problem faktoryzacji jest NP-zupełny? 16.08.10, 22:16 alsor: > Nie trzeba porównywać kilka razy jednego z innymi: Jednego czego z innymi czymi? alsor: > przeliczasz klucze na liczby Nie każde klucze dają się przeliczyć na liczby. Np. jeśli kluczami są nazwiska a porządek ma być alfabetyczny, to na liczby całkowite nie da się ich przeliczyć szybciej niż w n·log(n) a na rzeczywiste da się (z trudem) liniowo. Jednak na prawdziwe rzeczywiste, a nie na ich komputerowe przybliżenia. Dlatego mówiłem o sortowaniu przez porównania, a nie przez bardziej skomplikowane działania na kluczach. Ale nawet jeśli klucze już od początku są rzeczywiste, to można osiągnąć liniowy czas średni sortowania, jednak czas pesymistyczny nadal pozostanie n·log(n). alsor: > W innych problemach też da się zredukować złożoność, nawet NP - np. komiwojażer. Jeśli zredukujesz złożoność komiwojażera do wielomianowej, używając dowolnie wielkiej pamięci (ale tylko pojedynczego procesora), to clayowski milion dolarów jest Twój. Tyle że nie wykorzystasz efektywnie eksponencjalnej pamięci w czasie wielomianowym... - Stefan Odpowiedz Link Zgłoś
alsor Re: Czy problem faktoryzacji jest NP-zupełny? 17.08.10, 00:24 > > Nie trzeba porównywać kilka razy jednego z innymi: > > Jednego czego z innymi czymi? Podczas prostego sortowania porównujesz wiele razy jeden klucz z innymi, i stąd ta złożoność: n*log(n); albo n^2 w metodach prymitywnych. Kopiowań jest zwykle tyle samo, ale one są szybsze - zwłaszcza przy sortowaniu słów, czy zdań (dla dużych rekordów sortujemy wskaźniki, czyli 4 bajty sztuka, bo nie słyszałem o bazie 4 miliardów rekordów). > Np. jeśli kluczami są nazwiska a porządek ma być alfabetyczny, > to na liczby całkowite nie da się ich przeliczyć szybciej niż w n·log(n) a na rzeczywiste da się (z trudem) liniowo. Zły przykład. 1 litera = 1 bajt, albo dwa, czyli sortujesz zwyczajne liczby k-bajtowe - złożoność rzędu n; Liczby rzeczywiste w komputerze to tylko nazwa struktury - formatu, reprezentacji danych: [zccccccmmmmmmmmmmmmmmmm]; z - znak 1 bit; c, m - bity cechy i mantysy; czyli seria bitów, więc liczba całkowita od 0 do 2^n-1; n = 32, 64, ... > Jeśli zredukujesz złożoność komiwojażera do wielomianowej, > używając dowolnie wielkiej pamięci (ale tylko pojedynczego > procesora), to clayowski milion dolarów jest Twój. > Tyle że nie wykorzystasz efektywnie eksponencjalnej pamięci > w czasie wielomianowym... Wszystko da się zredukować, ale mówiłem - hardwerowo! Światło znajduje najszybszą trasę przez miliony soczewek w normalnym czasie... Odpowiedz Link Zgłoś
bimota Re: Czy problem faktoryzacji jest NP-zupełny? 17.08.10, 16:15 Podaj te algorytmy i sprawa sie wyjasni... Odpowiedz Link Zgłoś
artur.56 Re: Czy problem faktoryzacji jest NP-zupełny? 17.08.10, 18:30 alsor napisał: > Wszystko da się zredukować, ale mówiłem - hardwerowo! > > Światło znajduje najszybszą trasę przez miliony > soczewek w normalnym czasie... Czyli w najkrotszym.Tak,to prawda,w naturze nie istnieje pojecie trudnosci.Zasada najmniejszego dzialania jest tego faktu manifestacja.Wydaje sie ze tylko umysl ludzki jest jej oporny. "Hardwerowe wykorzystanie" przyrody widzimy we wspolczesnej elektronice.Nie jest wykluczonym,ze za iles lat bedziemy robic rzeczy ktorych dzialania nie rozumiemy ale umiemy je naprawic,czyli medycyna elektroniczna. Odpowiedz Link Zgłoś
bimota Re: Czy problem faktoryzacji jest NP-zupełny? 18.08.10, 13:37 Czyli, ze cos moze nalezec do NP i do P ? Zostalo powiedziane, ze do NP naleza zadania trudno rozwiazywalne, a do P latwo. To sie jakby wyklucza... Odpowiedz Link Zgłoś
asteroida2 Re: Czy problem faktoryzacji jest NP-zupełny? 18.08.10, 14:19 To źle zostało powiedziane. Do P należą problemy łatwo rozwiązywalne, a do NP - łatwo weryfikowalne, czyli takie, dla których mając podane rozwiązanie, łatwo sprawdzić że jest ono dobre. Z konieczności P zawiera się w NP, bo gdyby nie dało się łatwo sprawdzić rozwiązania to nie dałoby się też łatwo znaleźć dobrego. Odpowiedz Link Zgłoś
losiu4 Milion dolarów za nierówność 15.08.10, 20:06 "Teraz Deolalikar przedstawił na to twardy dowód. Kłopot w tym, że nie jest pewne, czy jest on pełny. W ciągu kilku dni matematycy znaleźli w nim kilka dziur." czyli jedną słową: na dziś dzień nic gość nie udowodnił. A hucpa jak to hucpa: jest mnóstwo ludzi którzy chcą "zaistniec". Jedni (a właściwie jedne) eksponują gołe cycki i d... tudziez pokazują swoją "postempowoźdź" puszczając się z kim popadnie, inni wolą sławę naukową... Pozdrawiam Losiu Odpowiedz Link Zgłoś
mary_sio Milion dolarów za nierówność 17.08.10, 18:26 Praca ma blisko 100 stron Cała praca łącznie z bibliografią ma 66 strony: www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pd Odpowiedz Link Zgłoś
slodier Re: Milion dolarów za nierówność 17.08.10, 18:36 mary_sio napisała: > >Praca ma blisko 100 stron >Cała praca łącznie z bibliografią ma 66 strony 0.66 =(w zaokragleniu do 1 miejsca) 0.7 = (zaokragleniu calkowitym) = 1.00 Po pomnozeniu obu stron przez 100 (co nie zmienia rownosci) 66 = 100 Zgadza sie teraz? Odpowiedz Link Zgłoś
mary_sio Re: Milion dolarów za nierówność 18.08.10, 16:38 Jasne! :-) Bardzo przepraszam... www.consulting360.pl/pl/blog-ekspercki/item/122-łowcy-pomyłek-z-allegro.html Odpowiedz Link Zgłoś
qual0play Milion dolarów za nierówność 18.08.10, 14:13 Jeżeli Kaczyński ma przeprosić Giertycha z wyroku Sądu, że kłamał i w tym celu wcześniej Sejm ma cofnąć immunitet, niech to to samo zrobi również Giertychowi a potem zaraz wszystkim politykom, jeżeli jako podstawę dla tego postanowienia uzna to, że polityk = kłamca. Odpowiedz Link Zgłoś