-
Data: 2010-08-13 15:55:47
Temat: Re: P != NP -- mamy dowod?
Od: Sebastian Kaliszewski <s...@r...this.informa.and.that.pl> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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)
Następne wpisy z tego wątku
- 14.08.10 11:45 Mariusz Marszałkowski
- 14.08.10 13:39 Marcin 'Qrczak' Kowalczyk
- 14.08.10 14:06 Mariusz Marszałkowski
- 20.08.10 15:16 Sebastian Kaliszewski
Najnowsze wątki z tej grupy
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
Najnowsze wątki
- 2024-10-04 Warszawa => QA Engineer <=
- 2024-10-04 Gdańsk => Specjalista ds. Sprzedaży <=
- 2024-10-04 Warszawa => Senior PHP Laravel Developer (e-commerce) <=
- 2024-10-04 Warszawa => Data Scientist / Data Engineer (predictive modelling) <=
- 2024-10-03 Nieparzyste dmuchanie
- 2024-10-03 Prognozowanie zużycia energii przez PGE?
- 2024-10-03 Re: Drugi ekran na Androidzie
- 2024-10-03 sprawiedliwosc nierychliwa
- 2024-10-03 zloto
- 2024-10-03 Odkurzacz mnie bije :(
- 2024-10-03 Gdańsk => Technical Lead ( (Java Background)) <=
- 2024-10-03 Warszawa => Mid IT Recruiter <=
- 2024-10-03 Olsztyn => Sales Specialist <=
- 2024-10-03 Leszczyna nie zna prawa?
- 2024-10-03 Warszawa => OpenText ECM Specialist <=