Problem FlowerVisit
XYZ: Czy problem jest NP−zupełny?
Truteń Gucio rozważa problem FlowerVisit (optymalne zbieranie nektaru ze wszystkich kwiatów
na łące). Po długim namyśle potrafi skonstruować redukcję w pamięci wielomianowej z problemu
HamPath (istnienie ścieżki Hamiltona w grafie) do problemu FlowerVisit. W związku
z tym jest przekonany, że problem FlowerVisit jest NP−zupełny.
Potwierdź przypuszczenia Gucia lub wyprowadź go z błędu. Odpowiedź uzasadnij.