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)