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

Usunięte 54 bajty ,  14 lat temu
m
pierwszy był SAT, a nie 3-SAT
m (drobne merytoryczne)
m (pierwszy był SAT, a nie 3-SAT)
'''Problem NP-zupełny''' (NPC) czyli [[problem zupełny]] w klasie [[Problem NP|NP]] ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym<ref>{{cytuj książkę |nazwisko=Papadimitriou |imię=Christos H |tytuł=Złożoność obliczeniowa | data=2002 |wydawca=Wydawnictwa Naukowo-Techniczne |miejsce=Warszawa |id=ISBN 83-204-2659-6 |strony=s. 182,192}}</ref>. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w czasie wielomianowym wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności).
 
Pierwszym problemem, którego NP-zupełność wykazano, był problem 3-[[Problem spełnialności|SAT]], czyli problem spełnialności wyrażeńformuł wzdaniowych. postaciUdowodnił 3CNFto (formuływ logiczne1971 składająceroku się[[Stephen z iloczynu logicznego 3-elementowych sum logicznych)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 problemu, nikomu się to nie udało.
146

edycji