Twierdzenie Cooka

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Twierdzenie Cooka-Levina – jedno z najważniejszych twierdzeń teorii złożoności obliczeniowej. Podaje ono pierwszy znany problem NP-zupełny. Od momentu jego udowodnienia można było stosować transformacje wielomianowe do dowodzenia NP-zupełności innych problemów decyzyjnych.

Teza[edytuj | edytuj kod]

Problem spełnialności formuł logicznych jest problemem NP-zupełnym.

Zobacz też[edytuj | edytuj kod]