eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingP != NP -- mamy dowod?
Ilość wypowiedzi w tym wątku: 7

  • 1. Data: 2010-08-11 12:28:40
    Temat: P != NP -- mamy dowod?
    Od: Roman Werpachowski <r...@g...com>

    http://www.hpl.hp.com/personal/Vinay_Deolalikar/Pape
    rs/pnp12pt.pdf

    Ten pan stawia $200,000 na to, ze dowod jest bledny:http://
    scottaaronson.com/blog/?p=456&

    RW


  • 2. Data: 2010-08-11 20:59:34
    Temat: Re: P != NP -- mamy dowod?
    Od: Mariusz Marszałkowski <m...@g...com>

    On 11 Sie, 14:28, Roman Werpachowski <r...@g...com>
    wrote:
    > http://www.hpl.hp.com/personal/Vinay_Deolalikar/Pape
    rs/pnp12pt.pdf
    >
    > Ten pan stawia $200,000 na to, ze dowod jest bledny:http://
    > scottaaronson.com/blog/?p=456&

    Przeczytałem kilka stron, z moim kiepskim angielskim połowy nie
    rozumiem. W pracy jest np. takie zdanie:

    If P != NP, we could never solve these problems efficiently.

    Czy na pewno ustalenie że P != NP oznacza brak efektywnych
    rozwiązań dla problemów NP? Załóżmy że ktoś udowodni
    iż P != NP, czy to będzie oznaczało również że nie da się np.
    znacznie zredukować podstawy potęgi w problemach NP?
    Albo czy to też będzie oznaczało że nie istnieje aproksymacyjny
    algorytm wielomianowy dający optymalne rozwiązanie z
    prawdopodobieństwem bliskim jeden?

    Pozdrawiam








  • 3. Data: 2010-08-13 15:55:47
    Temat: Re: P != NP -- mamy dowod?
    Od: Sebastian Kaliszewski <s...@r...this.informa.and.that.pl>

    Mariusz Marszałkowski wrote:
    > On 11 Sie, 14:28, Roman Werpachowski <r...@g...com>
    > wrote:
    >> http://www.hpl.hp.com/personal/Vinay_Deolalikar/Pape
    rs/pnp12pt.pdf
    >>
    >> Ten pan stawia $200,000 na to, ze dowod jest bledny:http://
    >> scottaaronson.com/blog/?p=456&
    >
    > Przeczytałem kilka stron, z moim kiepskim angielskim połowy nie
    > rozumiem. W pracy jest np. takie zdanie:
    >
    > If P != NP, we could never solve these problems efficiently.
    >
    > Czy na pewno ustalenie że P != NP oznacza brak efektywnych
    > rozwiązań dla problemów NP?

    Po pierwsze wiele przypadków NP-zupełnych może mieć rozwiązania z czasem
    wielomianowym dla typowych przypadków a tylko pesymistyczne przypadki
    mają czas wykładniczy.

    Po drugie dla wielu są całkiem dobre algorytmy aproksymacyjne, ale w
    paru (istotnych) przypadkach jest kłopot (o ile dobrze pamiętam np. z
    problemem komiwojażera) -- w paru przypadkach udowodniono, że np.
    aproksymacja gwarantująca wyniki nie gorszy niż np 1/2 optymalnego
    oznacza że automatycznie mamy rozwiązanie pełne. W związku z tym często
    lepiej jest zastosować rozwiązanie przybliżone bez gwarancji błędu
    (czyli takie którze może się pomylić znacznie) ale zwykle czy też dla
    naszych typowych danych, wystarczająco dobre.


    > Załóżmy że ktoś udowodni
    > iż P != NP, czy to będzie oznaczało również że nie da się np.
    > znacznie zredukować podstawy potęgi w problemach NP?

    W przypadku znanych nam NP zupełnych problem jest taki, że ich
    złożoności różnią się o wielomian i to zwykle niezbyt dużego stopnia.

    Własnością problemów NP-zupełnych jest to, że się wzajemnie do siebie
    redukują z wielomianowym narzutem (ogólnie wszystkie problemy z NP
    redukują się wielomianowo do NP-zupełnych ale NP-zupełne nie mają
    redukcji wielomianowych na te które nie są zupełne (jeśli w ogóle takie
    istnieją)). Dla popularnych problemów net narzut jest zwykle niezbyt duży.

    > Albo czy to też będzie oznaczało że nie istnieje aproksymacyjny
    > algorytm wielomianowy dający optymalne rozwiązanie z
    > prawdopodobieństwem bliskim jeden?

    Patrz wyżej.


    Generalnie dowiedzenie że P!=NP oznacza, że nie będzie się dało w
    sensownym czasie rozwiązać wielu problemów z gwarancją uzyskania
    optymalnego wyniku. Czyli, po prostu, że nie ma co liczyć na istotną
    poprawę sytuacji jaką mamy dziś (wszak dziś też nie umiemy tyle, że nie
    mamy pewności, że nie da się umieć).

    pzdr
    \SK
    --
    "Never underestimate the power of human stupidity" -- L. Lang
    --
    http://www.tajga.org -- (some photos from my travels)


  • 4. Data: 2010-08-14 11:45:25
    Temat: Re: P != NP -- mamy dowod?
    Od: Mariusz Marszałkowski <m...@g...com>

    On 13 Sie, 17:55, Sebastian Kaliszewski
    <s...@r...this.informa.and.that.pl> wrote:
    > Mariusz Marszałkowski wrote:
    > > On 11 Sie, 14:28, Roman Werpachowski <r...@g...com>
    > > wrote:
    > >>http://www.hpl.hp.com/personal/Vinay_Deolalikar/Pa
    pers/pnp12pt.pdf
    >
    > >> Ten pan stawia $200,000 na to, ze dowod jest bledny:http://
    > >> scottaaronson.com/blog/?p=456&
    >
    > > Przeczytałem kilka stron, z moim kiepskim angielskim połowy nie
    > > rozumiem. W pracy jest np. takie zdanie:
    >
    > > If P != NP, we could never solve these problems efficiently.
    >
    > > Czy na pewno ustalenie że P != NP oznacza brak efektywnych
    > > rozwiązań dla problemów NP?
    > Generalnie dowiedzenie że P!=NP oznacza, że nie będzie się dało w
    > sensownym czasie rozwiązać wielu problemów z gwarancją uzyskania
    > optymalnego wyniku. Czyli, po prostu, że nie ma co liczyć na istotną
    > poprawę sytuacji jaką mamy dziś (wszak dziś też nie umiemy tyle, że nie
    > mamy pewności, że nie da się umieć).

    Dziękuję za wyczerpującą odpowiedź. Zastanawiają mnie głównie trzy
    kwestie.
    1) Załóżmy że ktoś udowodni że P != NP. Więc żadnego problemu o
    rozmiarze danych wejściowych n i złożoności czasowej O(c_1^n) nie
    da się
    sprowadzić do złożoności O(n^c_2). Ale czy to będzie oznaczało
    również,
    że c_1 nie da się istotnie zredukować? Np. czy dowodu zero-
    jedynkowego
    nie da się przeprowadzić w czasie O(1.01^N)? Nadal złożoność jest
    wykładnicza
    ale nie taka nieefektywna. Od dawna przyglądam się problemowi
    przeszukiwania
    drzewa gry w grach GDZPIOSZ (gry dwuosobowe z pełną informacją o
    sumie zerowej).
    Np. konkretnie w szachach złożoność pełnego przeszukiwania wynosi
    około 35^N.
    (Nawiasem mówiąc, w literaturze można spotkać się z twierdzeniem,
    że GDZPIOSZ
    są tak trudne iż nawet programowanie dynamiczne nie pomaga w ich
    rozwiązaniu - to
    jest bzdura, pomaga i to bardzo). W szachach przeszukiwanie drzewa
    gry w celu
    odnalezienie najlepszego ruchu w najnowszych programach ma
    złożoność od
    około 2^N - 4^N - można to różnie liczyć, może nawet dokładniejsze
    jest
    oszacowanie 1.5^N, naprawę trudno jest dokładnie ustalić. Szachy
    to jeden szczególny
    przypadek gry, może się okazać że w szachach nawet da się
    przeszukiwanie
    drzewa zredukować do czasu wielomianowego i niczego rewelacyjnego
    to nie
    będzie oznaczało. Można zadać ciekawsze pytanie: czy dla każdej
    GDZPIOSZ można
    napisać algorytm o złożoności poniżej C^N, gdzie 1<C<<2. Czy dowód
    P != NP
    będzie również oznaczał że C>=2 ? Jeśli nie, to nadal jest
    nadzieja na efektywne
    rozwiązania.

    2) Druga sprawa to algorytmy aproksymacyjne i zrandomizowane. Jaką
    gwarancję błędu da
    się uzyskać w algorytmie wielomianowym? Albo jak da się
    zredukować prawdopodobieństwo
    że algorytm nie poda rozwiązania optymalnego? W przypadku
    udowodnienia że P != N nadal
    może istnieć algorytm aproksymacyjny działający w czasie
    wielomianowym dający optymalne
    rozwiązanie z prawdopodobieństwem dążącym do 1. Co z algorytmami
    które w czasie T dla
    danych o rozmiarze N dają optymalne rozwiązanie z
    prawdopodobieństwem P(T,N)
    P(T,N) = (1 / ( 1 + (N/(N+C))^T) - 0,5 ) * 2, gdzie 0<C. Czy
    udowodnienie P != NP także
    wykluczy istnienie takich algorytmów?

    3) Założywszy że faktycznie P != NP, to jak rośnie rozmiar S
    algorytmu w zależności od
    rozmiaru danych wejściowych N aby podawał rozwiązanie w czasie P?
    Dla małych
    problemów NP można stablicować wyniki i mamy rozwiązanie w czasie
    O(1). Problem w
    tym że rozmiar tablicy rośnie wykładniczo. Ale zamiast stałej
    tablicy z informacja jeden
    do jeden, można zapamiętać tablicę np. z samomodyfikującymi się
    regułami. Pytanie brzmi
    jak rośnie rozmiar S takiej tablicy aby czas wykonania algorytmu
    dla danych o rozmiarze
    mniejszym niż N był wielomianem C^N. Być może dla każdego problemu
    NP o rozmiarze
    mniejszym niż N, istnieje program o rozmiarze LOG(N) który daje
    rozwiązanie w czasie
    wielomianowym?

    Pozdrawiam





    Nie wiem, ale wydaje się że nawet jak się udowodni że P != NP to nadal
    pozostanie
    szansa na efektywne rozwiązywanie problemów.
























  • 5. Data: 2010-08-14 13:39:59
    Temat: Re: P != NP -- mamy dowod?
    Od: "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>

    On Aug 14, 1:45 pm, Mariusz Marszałkowski <m...@g...com> wrote:
    > 1) Załóżmy że ktoś udowodni że P != NP. Więc żadnego problemu o
    >     rozmiarze danych wejściowych n i złożoności czasowej O(c_1^n) nie
    > da się
    >     sprowadzić do złożoności O(n^c_2).

    Jedno nie ma z drugim nic wspólnego.

    Po pierwsze notacja O() oznacza ograniczenie z góry. Jeśli jest
    O(n^2), to jest też O(2^n); odwrotnie niekoniecznie. Zatem oczywiście
    istnieją problemy w O(c_1^n), które są też w O(n^c_2); mianowicie
    wszystkie w O(n^c_2).

    Po drugie nie każdy problem, który można rozwiązać w czasie
    wykładniczym, jest w NP. Więc nawet jeśli P = NP, to nie oznacza to,
    że jeśli problem jest w O(c_1^n), to jest w O(n^c_2).

    http://en.wikipedia.org/wiki/EXPTIME

    > Ale czy to będzie oznaczało
    > również,
    >     że c_1 nie da się istotnie zredukować? Np. czy dowodu zero-
    > jedynkowego
    >     nie da się przeprowadzić w czasie O(1.01^N)?

    1.01^N ? 2^(70*N). 2^N i 1.01^N to jest ta sama klasa złożoności, bo
    skala N jest umowna.


  • 6. Data: 2010-08-14 14:06:31
    Temat: Re: P != NP -- mamy dowod?
    Od: Mariusz Marszałkowski <m...@g...com>

    On 14 Sie, 15:39, "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>
    wrote:
    > On Aug 14, 1:45 pm, Mariusz Marszałkowski <m...@g...com> wrote:
    >
    > > 1) Załóżmy że ktoś udowodni że P != NP. Więc żadnego problemu o
    > >     rozmiarze danych wejściowych n i złożoności czasowej O(c_1^n) nie
    > > da się
    > >     sprowadzić do złożoności O(n^c_2).
    >
    > Jedno nie ma z drugim nic wspólnego.

    > Po pierwsze notacja O() oznacza ograniczenie z góry. Jeśli jest
    > O(n^2), to jest też O(2^n); odwrotnie niekoniecznie. Zatem oczywiście
    > istnieją problemy w O(c_1^n), które są też w O(n^c_2); mianowicie
    > wszystkie w O(n^c_2).
    Sorry, miała być omega, chodziło oczywiście minimalny czas.

    > 1.01^N ? 2^(70*N). 2^N i 1.01^N to jest ta sama klasa złożoności, bo
    > skala N jest umowna.

    Odwrotnie: 1.01^N ? 2^(N/70).
    Chyba nie jest to samo, bo nie istnieje żadne C>0 dla którego C*1.01^N
    > 2^N
    dla dowolnie dużych N? Trzeba wymnożyć N przez współczynnik 0.14,
    czyli
    w praktyce można efektywnie (w tym samym czasie) rozwiązać problemy 70
    razy
    większe.

    Pozdrawiam


  • 7. Data: 2010-08-20 15:16:19
    Temat: Re: P != NP -- mamy dowod?
    Od: Sebastian Kaliszewski <s...@r...this.informa.and.that.pl>

    Mariusz Marszałkowski wrote:
    > On 13 Sie, 17:55, Sebastian Kaliszewski
    > <s...@r...this.informa.and.that.pl> wrote:
    >> Mariusz Marszałkowski wrote:
    >>> On 11 Sie, 14:28, Roman Werpachowski <r...@g...com>
    >>> wrote:
    >>>> http://www.hpl.hp.com/personal/Vinay_Deolalikar/Pape
    rs/pnp12pt.pdf
    >>>> Ten pan stawia $200,000 na to, ze dowod jest bledny:http://
    >>>> scottaaronson.com/blog/?p=456&
    >>> Przeczytałem kilka stron, z moim kiepskim angielskim połowy nie
    >>> rozumiem. W pracy jest np. takie zdanie:
    >>> If P != NP, we could never solve these problems efficiently.
    >>> Czy na pewno ustalenie że P != NP oznacza brak efektywnych
    >>> rozwiązań dla problemów NP?
    >> Generalnie dowiedzenie że P!=NP oznacza, że nie będzie się dało w
    >> sensownym czasie rozwiązać wielu problemów z gwarancją uzyskania
    >> optymalnego wyniku. Czyli, po prostu, że nie ma co liczyć na istotną
    >> poprawę sytuacji jaką mamy dziś (wszak dziś też nie umiemy tyle, że nie
    >> mamy pewności, że nie da się umieć).
    >
    > Dziękuję za wyczerpującą odpowiedź. Zastanawiają mnie głównie trzy
    > kwestie.
    > 1) Załóżmy że ktoś udowodni że P != NP. Więc żadnego problemu o
    > rozmiarze danych wejściowych n i złożoności czasowej O(c_1^n) nie
    > da się
    > sprowadzić do złożoności O(n^c_2).

    Poza różnicami notacyjnymi to jest parę innych klas dla których albo
    wiemy (EXPTIME -- z definiji) albo podejrzewamy, że czas jest
    wykładniczy -- najbardziej znane to NP, coNP, PSPACE (pamięć
    wielomianowa) i EXPTIME w dodatku wiadomo że NP i coNP są podklasami
    (Ale nie wiadomo czy właściwymi czy też są równe) PSPACE a PSPACE jest
    podklasą EXPTIME. Wiadomo też (z definicji w przypdku NP i EXPTIME i z
    prostego dowodu w pozostałych przypadkach) że P jest podklasą NP, coNP,
    PSPACE i EXPTIME ale to że jest podklasą właściwą (nie jest równe)
    wiadomo tylko w relacji do EXPTIME (znów z definicji).

    > Ale czy to będzie oznaczało
    > również,
    > że c_1 nie da się istotnie zredukować? Np. czy dowodu zero-
    > jedynkowego
    > nie da się przeprowadzić w czasie O(1.01^N)? Nadal złożoność jest
    > wykładnicza
    > ale nie taka nieefektywna.

    Zysk w wielkości danych 70x -- to nie jest dużo to ledwie parę lat
    rozwoju komputerów. To już lepiej np 2^sqrt(N) albo 2^log^2(N) -- ale
    może wyjść że się nie da... (nie wiadomo na razie co się da -- najpierw
    to w ogóle musi być jakikolwiek dowód)

    > Od dawna przyglądam się problemowi
    > przeszukiwania
    > drzewa gry w grach GDZPIOSZ (gry dwuosobowe z pełną informacją o
    > sumie zerowej).

    Ogólny problem roziwiązania szachów jest EXPTIME zupełny. czyli wiadomo,
    że jest wykłądniczy i koniec. Ogólny, czyli dla uogólnionych szachów o N
    polach na szachownicy.


    > Np. konkretnie w szachach złożoność pełnego przeszukiwania wynosi
    > około 35^N.

    Ale co to jest N w tym wypadku -- to rozmiar czego?

    > (Nawiasem mówiąc, w literaturze można spotkać się z twierdzeniem,
    > że GDZPIOSZ
    > są tak trudne iż nawet programowanie dynamiczne nie pomaga w ich
    > rozwiązaniu - to
    > jest bzdura, pomaga i to bardzo). W szachach przeszukiwanie drzewa
    > gry w celu
    > odnalezienie najlepszego ruchu w najnowszych programach ma
    > złożoność od
    > około 2^N - 4^N - można to różnie liczyć, może nawet dokładniejsze
    > jest
    > oszacowanie 1.5^N, naprawę trudno jest dokładnie ustalić. Szachy
    > to jeden szczególny
    > przypadek gry, może się okazać że w szachach nawet da się
    > przeszukiwanie
    > drzewa zredukować do czasu wielomianowego i niczego rewelacyjnego
    > to nie
    > będzie oznaczało. Można zadać ciekawsze pytanie: czy dla każdej
    > GDZPIOSZ można
    > napisać algorytm o złożoności poniżej C^N, gdzie 1<C<<2. Czy dowód
    > P != NP
    > będzie również oznaczał że C>=2 ? Jeśli nie, to nadal jest
    > nadzieja na efektywne
    > rozwiązania.

    Jeśli zostanie samo N w wykładniku to wszystko jedno -- i tak będzie
    słabo. Ale może gdzieś bedzie np. sqrt(N) -- to już jest lepiej.

    Tyle tylko, że problem uogólnionych szachów jest EXPTIME trudny a nie
    NP-trudny -- czyli z góry wiadomo że jest i pozostanie wykładniczy.


    > 2) Druga sprawa to algorytmy aproksymacyjne i zrandomizowane. Jaką
    > gwarancję błędu da
    > się uzyskać w algorytmie wielomianowym?

    To zależy od problemu -- dla niektórych daje się określić gwarantowany
    maksymalny błąd na np 1/2 poszukiwanej wielkości a dla niektórcyh to
    jest dużo gorzej (np 1/N).

    > Albo jak da się
    > zredukować prawdopodobieństwo
    > że algorytm nie poda rozwiązania optymalnego? W przypadku
    > udowodnienia że P != N nadal
    > może istnieć algorytm aproksymacyjny działający w czasie
    > wielomianowym dający optymalne
    > rozwiązanie z prawdopodobieństwem dążącym do 1.

    No właśnie nie jest to takie oczywiste -- to by zależało od tego czy
    parę klas raddomizacyjnych (a jest tego trochę zależnie od tego, czy
    dopszczamy np. tylko "niedostrzelenie" wyniku czy zarówno
    "niedopstrzelenie" jak i "przestrzelenie") okazało by się równych lub
    nie równych NP.

    Co z algorytmami
    > które w czasie T dla
    > danych o rozmiarze N dają optymalne rozwiązanie z
    > prawdopodobieństwem P(T,N)
    > P(T,N) = (1 / ( 1 + (N/(N+C))^T) - 0,5 ) * 2, gdzie 0<C. Czy
    > udowodnienie P != NP także
    > wykluczy istnienie takich algorytmów?
    >
    > 3) Założywszy że faktycznie P != NP, to jak rośnie rozmiar S
    > algorytmu w zależności od
    > rozmiaru danych wejściowych N aby podawał rozwiązanie w czasie P?
    > Dla małych
    > problemów NP można stablicować wyniki i mamy rozwiązanie w czasie
    > O(1). Problem w
    > tym że rozmiar tablicy rośnie wykładniczo. Ale zamiast stałej
    > tablicy z informacja jeden
    > do jeden, można zapamiętać tablicę np. z samomodyfikującymi się
    > regułami. Pytanie brzmi
    > jak rośnie rozmiar S takiej tablicy aby czas wykonania algorytmu
    > dla danych o rozmiarze
    > mniejszym niż N był wielomianem C^N. Być może dla każdego problemu
    > NP o rozmiarze
    > mniejszym niż N, istnieje program o rozmiarze LOG(N) który daje
    > rozwiązanie w czasie
    > wielomianowym?

    Tego też nie wiadomo. Pi*drzwi opisałeś coś co byłoby podklasą klasy
    nonuniform-P -- czyli taką gdzie wielkość samego zapisu algorytmu zależy
    wielomianowo od N a czas obliczenia jest P.

    Dla tej klasy jest ciekawy wynik negatywny -- otóż udowodniono, że o ile
    istnieją przyzwoite generatory pseudolosowe (a wydaje się, że istnieją
    -- gdyby nie istniały to zdaje się że byłby prosty dowód na P==NP) to
    nie istnieje naturalny dowód na to czy ta klasa jest równa czy różna od
    NP. Dowód naturalny to taki który da się przeprowadzić na gruncie
    teorii mnogości i logiki, bez wychodzenia do jakiś "obcych" teorii (np.
    dot. liczb rzeczywistych czy krzywych eliptycznych -- z pomocą tych
    ostatnich np. dowiedziono Wielkie Twierdzenie Fermata). Problem taki, że
    nawet nie bardzo wiadomo jak w ogóle zmapować problem P!=NP na takie
    "nienaturalne" twory.

    Jest to jedna z 3 udowodnionych barier dot. dowodu P vs NP. Pierwsza to
    bariara tzw. relatywizacji, 2 (chronologicznie) to właśnie ww. zaś
    trzecia to niedawny (1-2 lata) wynik dot. algebraizacji (czylio jakby
    nawet jakość skojarzyć z problemami jakieś "nienaturalne" twory
    algebraiczne to i tak guzik wyjdzie). Z powyższego wynika, że albo dowód
    będzie niezwykle przekrojowy, sięgający do obcych i na oko niezwiązanych
    teorii albo też będzie musiał w decydujący sposób skorzystać z faktu, że
    wielkość algorytmu musi być stała (to już jest istotna podpowiedź).

    Dodatkowo podejrzewa się że ta klasa może być równa P (ale te
    podejrzenia są słabsze niż to że P != NP). Ogólnie to wiadomo że P <=
    nonuniformP <= NP.

    > Nie wiem, ale wydaje się że nawet jak się udowodni że P != NP to nadal
    > pozostanie
    > szansa na efektywne rozwiązywanie problemów.

    Udowodnienie P != NP oznaczać będzie istnienie twardych ograniczeń
    również na rozwiązania przybliżone.


    pzdr
    \SK
    --
    "Never underestimate the power of human stupidity" -- L. Lang
    --
    http://www.tajga.org -- (some photos from my travels)

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: