Dlaczego ważne jest, aby udowodnić, że problem dotyczy NP?

Czy mam rację rozumiejąc, że udowodnienie, że problem NP jest kompletny, to sukces badawczy? Jeśli tak to dlaczego?

Ali, dobre pytanie.

Załóżmy, że chcesz pokazać, że jakiś problem P jest trudny obliczeniowo. Teraz możesz przypuszczać, że P jest trudne tylko na podstawie faktu, że nie mamy jeszcze wydajnych algorytmów. Ale to raczej wątły dowód, nie? Możliwe, że przegapiliśmy jakiś fajny sposób patrzenia na P, który bardzo ułatwiłby jego rozwiązanie. Aby więc przypuszczać, że P jest trudne, chcielibyśmy zgromadzić więcej dowodów. Redukcje zapewniają narzędzie do tego dokładnie! Jeśli możemy zredukować jakiś inny naturalny problem Q do P, to pokazaliśmy, że P jest co najmniej tak samo trudny jak Q. Ale Q może być problemem z zupełnie innej dziedziny matematyki, a ludzie od dziesięcioleci mogą walczyć o rozwiązanie Q . Zatem możemy uznać, że nasze niepowodzenie w znalezieniu wydajnego algorytmu dla Q jest dowodem na to, że P jest trudne. Jeśli mamy dużo takich Q '

Dokładnie to zapewnia teoria kompletności NP. Jeśli udowodnisz, że twój problem jest NP-zupełny, to powiązałeś jego twardość z twardością setek innych problemów, z których każdy ma istotne znaczenie dla różnych społeczności. Tak więc, mówiąc moralnie, możesz być pewien, że twój problem jest naprawdę trudny.

Udowadnianie problemu NP-Complete jest sukcesem badawczym, ponieważ uwalnia cię od konieczności szukania wydajnego i dokładnego rozwiązania ogólnego problemu, który studiujesz. Dowodzi to, że twój problem należy do klasy problemów tak trudnych, że nikt nie był w stanie znaleźć wydajnego i dokładnego algorytmu dla któregokolwiek z problemów, a takie rozwiązanie dla któregokolwiek z problemów oznaczałoby rozwiązanie dla wszystkich problemy.

Zwykle jest to odskocznia, ponieważ twój problem wciąż istnieje - po prostu musisz rozluźnić swoje wymagania. Zwykle ludzie próbują dowiedzieć się, jak zrelaksować jeden lub więcej „skutecznych”, „dokładnych” lub „ogólnych”. Nieefektywnym i dokładnym i ogólnym jest próba znalezienia coraz lepszych stałych w wykładniku dla tych algorytmów. Skuteczne i niedokładne i ogólne jest badanie algorytmów aproksymacyjnych. Skuteczne i dokładne, ale nie ogólne jest badanie wykonalności stałych parametrów i poszukiwanie podklas danych wejściowych, dla których można znaleźć wydajne algorytmy.

$NP-complete$

$NP-complete$, masz pewne dowody na to twoje przypuszczenie i powinieneś zacząć rozważać alternatywne podejście (np. zmienić problem, aby stał się łatwiejszy).

$NP-complete$

$NP-complete$

$P=NP$$3-SAT$

$NP-complete$$CLIQUE$

Podsumowując, charakterystyka problemu pozwala na użycie typowych technik. Studiując klasę, z którą jest związana, możesz myśleć abstrakcyjnie, nie zawracając sobie głowy specyfiką tego konkretnego problemu, który jest powszechny w matematyce i nauce w ogóle. Praca z klasami zamiast z poszczególnymi elementami pozwala na wykorzystanie znanych technik, a ponadto zastosowanie wglądu do większej liczby obiektów, zamiast tylko jednego.

Każdy problem ma kilka powiązań z innymi problemami. Ponadto istnieją relacje między klasami problemu i złożoności.

Dlatego sklasyfikowanie jednego problemu jako NPC zwykle daje nam wgląd w inne problemy, a także klasy złożoności.

Weźmy na przykład problem z izomorfizmem grafowym (GI). W następującym artykule:

Uwe Schöning, Graf izomorfizm ma niską hierarchię , Proceedings of 4th Annual Symposium on Theoretical Aspects of Computer Science , 1987, 114–124; także: Journal of Computer and System Sciences, vol. 37 (1988) 312–323.

udowodniono, że jeśli GI ∈ NPC, hierarchia wielomianowa (PH) załamie się na swój drugi poziom; co będzie dużym przełomem w teorii złożoności strukturalnej.

$p$$p$$p$$p$