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

do góry

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

do góry

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)

do góry

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.

do góry

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.

do góry

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

do góry

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)

do góry