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.