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