Zadania

NP - klasa algorytmów problemów decyzyjnych, dJa kiótych istnieje ograniczony widomi a nowo algorytm ni edetermi nistyczny

P=NP ⁹ Czy niedeterminizm jest silniejszy' niż detenninizm, czy znalezienie dowodu jest trudniejsze niż jego weryfikacja Problem n jest NPC jeżeli jest NP i jeżeli dla każdego innego IT mamy IT a FI.

Aby dowieźć, że n jest NPH musimy : znaleźć znany jako NPC problem PT, zredukować JT do n np. FT a IX

wywnioskować z poprzednich myślników, że wszystkie problemy w NPC mogą być zredukowane do IX by dowieźć, że jest NPC musimy albo pokazać, że Fis NP, albo Flank Problemy optymalizacyjne nie mogą być NPC, ale mogą być NPH. Istnieją także decyzyjne problemy NPH, które nie są NPC.

60* Złożoność problemów

faktoryzacja - niewielomianowy NPI (liczba pierwsza),

dzielenie liczb - wielomianowy

wieże w Hanoi - T

2SAT - wielomianowy

3SAT-NPC

mnożenie macieży - wielomian G(n)

sortowanie - nlogm

cykl Eulera - 0(n)

minmax - 0(n)

element na liście - 0(n)

listowanie wszystkich ustawień n - 0(n!)

komiwojażer - niewielomianowy

kolorowanie grafu - niewielomianowy

izomorfizm grafów - NPI

gdy P=NP, to NPeP