Milion dolarów za nierówność

13.08.10, 16:17
To też teoria: P=/=NP N i P= NIP.
    • 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.
    • 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
      • 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/
        • 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
          • 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ę'?
            • 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
              • 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?

              • 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.
          • neuromancer0 Re: Nie interesuja mnie pierwsze reakcje 13.08.10, 23:36
            Hahaha, ale się uśmiałem z tego posta :D
            • mamula66 Re: Nie interesuja mnie pierwsze reakcje 14.08.10, 01:09
              ja tez!
              • neuromancer0 Re: Nie interesuja mnie pierwsze reakcje 14.08.10, 21:10
                Ja mówiłem o Twoim poście :P
    • 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
      • 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.
        • 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.
          • 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".
    • 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 ??
    • 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
      • 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.
        • 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.
          • 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...
          • 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?
            • 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...
          • 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)
            • 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.
              • 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
                • 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...
                  • bimota Re: Czy problem faktoryzacji jest NP-zupełny? 17.08.10, 16:15
                    Podaj te algorytmy i sprawa sie wyjasni...
                  • 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.
      • 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...
        • 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.
    • 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
    • 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
      • 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?

        • 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
    • 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.
Inne wątki na temat:
Pełna wersja