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)