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).

Po drugie nie każdy problem, który można rozwiązać w czasie
wykładniczym, jest w NP. Więc nawet jeśli P = NP, to nie oznacza to,
że jeśli problem jest w O(c_1^n), to jest w O(n^c_2).

http://en.wikipedia.org/wiki/EXPTIME

> Ale czy to będzie oznaczało
> również,
>     że c_1 nie da się istotnie zredukować? Np. czy dowodu zero-
> jedynkowego
>     nie da się przeprowadzić w czasie O(1.01^N)?

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.