-
Data: 2010-08-11 20:59:34
Temat: Re: P != NP -- mamy dowod?
Od: Mariusz Marszałkowski <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 13.08.10 15:55 Sebastian Kaliszewski
- 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-07-02 Realme 7 Na co zmienić?
- 2024-06-27 Prywatny parking? Pierwsze 10 minut bezplatnie
- 2024-07-02 znalazłem samochód ;)
- 2024-07-02 Pierwszeństwo łamane
- 2024-07-02 zamek
- 2024-07-02 Akumulatory VRLA
- 2024-07-03 Białystok => Inżynier DevOps Conexa First (Kontraktor) <=
- 2024-07-03 MĂźnchen => Test Development Engineer (m/w/d) <=
- 2024-07-03 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-07-03 Warszawa => Programista Full Stack (.Net Core) <=
- 2024-07-02 Kraków => Spedytor międzynarodowy <=
- 2024-07-02 Poznań => Senior React Native Developer <=
- 2024-07-02 Rzeszów => Frontend Developer (React) <=
- 2024-07-02 Warszawa => Fullastack (Java) Developer <=
- 2024-07-02 reparacje