On 14 Sie, 15:39, "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>
wrote:
> On Aug 14, 1:45 pm, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > 1) Załóżmy że ktoś udowodni że P != NP. Więc żadnego problemu o
> >     rozmiarze danych wejściowych n i złożoności czasowej O(c_1^n) nie
> > da się
> >     sprowadzić do złożoności O(n^c_2).
>
> Jedno nie ma z drugim nic wspólnego.

> Po pierwsze notacja O() oznacza ograniczenie z góry. Jeśli jest
> O(n^2), to jest też O(2^n); odwrotnie niekoniecznie. Zatem oczywiście
> istnieją problemy w O(c_1^n), które są też w O(n^c_2); mianowicie
> wszystkie w O(n^c_2).
Sorry, miała być omega, chodziło oczywiście minimalny czas.

> 1.01^N ? 2^(70*N). 2^N i 1.01^N to jest ta sama klasa złożoności, bo
> skala N jest umowna.

Odwrotnie: 1.01^N ? 2^(N/70).
Chyba nie jest to samo, bo nie istnieje żadne C>0 dla którego C*1.01^N
> 2^N
dla dowolnie dużych N? Trzeba wymnożyć N przez współczynnik 0.14,
czyli
w praktyce można efektywnie (w tym samym czasie) rozwiązać problemy 70
razy
większe.

Pozdrawiam