Wersja z 16:16, 12 maj 2015 edytuj Daroooo (dyskusja \| edycje) Redaktorzy 7642 edycje m lit. Znacznik: VisualEditor ← poprzednia edycja		Wersja z 18:56, 12 maj 2015 edytuj anuluj edycję Daroooo (dyskusja \| edycje) Redaktorzy 7642 edycje m drobne redakcyjne następna edycja →
Linia 3: Pierwszym problemem, którego NP-zupełność wykazano, był problem [[Problem spełnialności\|SAT]], czyli problem spełnialności formuł zdaniowych. Udowodnił to w 1971 roku [[Stephen Cook]]. Pytanie, czy problemy NP-zupełne można rozwiązywać w czasie wielomianowym, jest największą zagadką informatyki teoretycznej. Ciągle nie udowodniono tego, iż <math>P\not=NP\,</math> (nie udowodniono także przeciwnie, że <math>P=NP\,</math>), która jednoznacznie stwierdzałaby, że jest to niemożliwe. Rozwiązanie tego problemu znalazło się na liście [[problemy milenijne\|problemów milenijnych]]. Mimo ufundowania miliona dolarów za rozwiązanie tak postawionego problemu, nikomu się to nie udało. Pytanie związane z problemami NP-zupełnymi ma szczególne znaczenie w [[kryptografia\|kryptografii]] – rozwiązanie któregokolwiek problemu NP-zupełnego w czasie wielomianowym (a zatem rozwiązanie ich wszystkich) umożliwiłoby między innymi szybkie łamanie kryptosystemu [[RSA (kryptografia)\|RSA]] (jednego z najbardziej popularnych szyfrów aktualnie stosowanych), gdyż opiera się on na założeniu, że problem podziału dowolnej liczby na czynniki pierwsze nie jest [[problem P\|problemem wielomianowym]]. Problem ten jest w NP, ale nie udowodniono jego NP-trudności. Problem nie może być jednocześnie NP-zupełny i [[Klasa Co-NPC\|CoNP-zupełny]], chyba że <math>NP=CoNP\,</math>. ==Przykłady== Linia 20: [[cykliczne pokrycie krawędziowe]] [[problem plecakowy\|decyzyjna wersja problemu plecakowego]] {{Przypisy}}▼ == Zobacz też == * p[[Problem NP-trudny\|~~roblem~~problem NP-trudny]] * p[[Problem silnie NP-zupełny\|~~roblem~~problem silnie NP-zupełny]] * l[[Lista problemów NP-zupełnych\|~~ista~~lista problemów NP-zupełnych]] * [[problem NP-pośredni]] * p[[Problem obliczeniowy\|~~roblem~~problem obliczeniowy]] ▲{{Przypisy}} [[Kategoria:Teoria obliczeń]]

Problem NP-zupełny: Różnice pomiędzy wersjami