@vpiotr co ty gadasz? Jaka magisterka? To są przecież zadania na 15 minut. Widzę że ktoś znów przespał Teorię Złożoności Obliczeniowej :D
@kamis159 a ty łaskawie mógłbyś podać sensowne nazwy dla tych problemów. Zgaduje że twoje UHAMPATH to nieskierowana ścieżka hamiltona (http://en.wikipedia.org/wiki/Hamiltonian_path_problem) a LPATH to najdłuższa ścieżka (http://en.wikipedia.org/wiki/Longest_path_problem)?
Deterministycznej wielomianowej maszyny to nie zrobisz, chyba że udowodnisz że P=NP i zgadniesz milion dolarów :D
Dla maszyny niedeterministycznej to nie ma specjanie wiekiego problemu. Na przykład dla longest-path robisz pętlę po każdym wierzchołku szukając "początkowego" a następnie podejmujesz decyzję którą krawędzią iśc. Maszyna niedeterministyczna pozwala "zgadywać", więc po prostu na każdym rozgałęzieniu bierzesz "dobrą" ścieżkę. W efekcie masz złożoność O(V*E).
Analogicznie na to "zgadywanie" można patrzeć tak, że maszyna potrafi rozgałęziać obliczenia i prowadzić je równolegle. Więc w każdym wierzchołku możemy rozgałęzić obliczenia dla każdej krawędzi i prowadzić je równolegle a na koniec wybrać tą opcje która dała najlepszy wynik.