pytanie do studentów informatyki - POMOCY !

[Gość: zły]

Proszę o definicję "niedeterministycznej złożoności wielomianowej" - nie
mylić ze złożonością wielomianową, to wydaje mi się, że ma jakiś związek z
maszyną Turinga i tezą Churcha-Turinga - w książce Harela nie ma konkretnego
wyjaśnienia tej definicji, także proszę o pomoc - pytanie kieruje zwłaszcza
do Lolka niezłego - może ty wiesz? :(

[Gość: Lol_niezly]

Teza Churcha-Turinga mowi tyle, ze dowolna, ogolna metoda obliczania pozwala na
obliczanie jedynie funkcji czesciowo rekurencyjncyh.

Moze tak: na komputerze lub maszynie Turinga( wszystko jedno) mozemy obliczac
tylko niektore problemy.Niektore, ktorych nie da sie rozwiazac w czasie
wielomianowym wzgledem wejscia nazywamy problemami klasy NP lub
nierozstrzygalnymi jak wolisz ;)Ogolnie pomiedzy funkcja wielomianowa i
wykladnicza nie ma nic - jest jakis logarytm, ale on i tak predzej czy pozniej
zliza sie do funkcji wykladniczej.Problemy nierozstrzygalne sa to problemy
ktore "mozna" rozwiazac za pomoca niedeterministycznej maszyny Turinga
pracujacej w czasie wielomianowym.Tzn. jesli jakis problem ma
niedeterministyczna zlozonosc wielomianowa to jest klasy NP np: problem
kombiwojażera.

Formalnie mozna to okreslic tak:
Jezyk L jest klasy NP, jesli istnieje niedeterministyczna maszyna Turinga(M) i
wielomianowa zlozonosc czasowa T(n) taka, ze L=L(M) oraz po wczytaniu wejscia o
dlugosci n maszyna M nie wykonuje ciagu ruchow dluzszego niz T(n).

Zaznaczam ze mowie o niedeterministycznej czasowej zlozonosci wielomianowej.
Innej nie znam i prawdopodobnie o ta Ci tez chodzi :)

[Gość: zły]

Lolek dzięki, jesteś wielki - m. in. takie pytanie było na egzaminie ze wstępu
do infy, który zdaje u nas za pierwszym razem 10% osób - ja będę zapewne wśród
90% które nie zdadza za pierwszym razem - chory jest ten wstęp do infy i chyba
do niczego nie przydatny ;P, te problemy jedzących filozofów, drzew, kolejek,
stosów itd. - dzięki lolku - fajny przekręt zrobiłeś w jednym słowie -
"kombiwojażer" zamiast "komiwojażera"- to napewno zwykła pomyłka przy szybkim
pisaniu, ale śmiesznie wyszło :D jeszze raz ślicznei ci dziękuję

[lol_niezly]

Prosze :)
Zycze samych zdanych egzaminow i powodzenia :]

[Gość: HellHax]

chinski kombiwojażer roxx:)