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
Problem spełnialności formuł logicznych jest problemem NP-zupełnym.
Zobacz też
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.