Problem NP: Różnice pomiędzy wersjami

Dodane 30 bajtów ,  15 lat temu
brak opisu edycji
Nie podano opisu zmian
Nie podano opisu zmian
 
W szczególności wszystkie [[problem P|problemy klasy '''P''']] są '''NP''', ponieważ można je sprawdzić w czasie [[wielomian]]owym.
Innymi słowy, [[problem P|klasa '''P''']] zawiera się nieostro w '''NP'''.
(<math>P \subseteq NP</math>).
Nie wiadomo natomiast, czy istnieje problem '''NP''', który nie jest w klasie '''P'''
(czyli, czy '''P''' rożni się od '''NP''').
Anonimowy użytkownik