-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!plix.pl!newsfeed1.plix.pl!newsfeed00.su
l.t-online.de!t-online.de!news1.as3257.net!nx02.iad01.newshosting.com!newshosti
ng.com!newsfeed.neostrada.pl!unt-exc-01.news.neostrada.pl!unt-spo-a-01.news.neo
strada.pl!news.neostrada.pl.POSTED!not-for-mail
Date: Fri, 13 Aug 2010 17:55:47 +0200
From: Sebastian Kaliszewski <s...@r...this.informa.and.that.pl>
User-Agent: Thunderbird 2.0.0.24 (X11/20100411)
MIME-Version: 1.0
Newsgroups: pl.comp.programming
Subject: Re: P != NP -- mamy dowod?
References: <7...@t...googlegroups.com>
<6...@j...googlegroups.com>
In-Reply-To: <6...@j...googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-2; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <e...@b...softax.pl>
Lines: 62
Organization: Telekomunikacja Polska
NNTP-Posting-Host: 83.18.189.42
X-Trace: 1281715202 unt-rea-b-01.news.neostrada.pl 22815 83.18.189.42:46524
X-Complaints-To: a...@n...neostrada.pl
Xref: news-archive.icm.edu.pl pl.comp.programming:186497
[ ukryj 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
- 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
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-06-27 Re: Prywatny parking? Pierwsze 10 minut bezplatnie
- 2024-06-27 A co mnie to koooorwa obchodzi?
- 2024-06-28 nawigacja satelitarna
- 2024-06-28 SmartLife/Tuya i osuszanie -- mordowanie z zimną krwią...
- 2024-06-27 położyłem kafelki
- 2024-06-28 Łódź => International Freight Forwarder <=
- 2024-06-28 Łódź => Spedytor Międzynarodowy <=
- 2024-06-28 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-06-28 Sopot => Team Leader E-Commerce for Foreign Markets <=
- 2024-06-28 Warszawa => Senior React Native Developer <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=
- 2024-06-28 Warszawa => Software .Net Developer <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=
- 2024-06-28 Warszawa => Programista Full Stack .Net <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=