mamy do rozwiazania problem
musimy podzielic pewna liczbe osob na trzy grupy;
kazda osoba przygotowuje liste osob ktorych nie lubi;
dzielimy wszystkie osoby na 3 grupy w taki sposob by w zadnej grupie nie było nawet 2 nielubiacych sie osob;
musze udowodnic ze ten problem nalezy do grupy problemow np-zupelnych.
Prosze o pomoc
Problem może być NP-zupełny, nie algorytm.
A pytanie gdzie? Rozumiem że pytasz "jak dowodzi się NP-zupełności"?
Otóż dowód taki wymaga 2 kroków, wynikających bezpośrednio z definicji:
Problem NP-zupełny to problem który:
Ad.1. dowieść jest zwykle banalnie łatwo, w tym przypadku:
Nasz algorytm dokonuje podziału osób na 3 grupy a następnie sprawdzamy czy nie występują w żadnej z grup 2 lub więcej nielubiących się osób. Niedeterministyczna maszyna turinga potrafi z definicji rozpatrywać nam wiele ścieżek jednocześnie, w efekcie potrafi rozwiązać ten problem w czasie O(n) [oczywiście deterministyczna maszyna turinga z tym algorytmem wymagałaby wykładniczego czasu, bo byłaby to zwykła rekurencja z powrotami]
Ad.2. z tym zwykle bywa trudniej, bo najprostszym sposobem jest wielomianowa redukcja znanego problemu NP-zupełnego do naszego problemu. Tzn musimy pokazać że pewien znany problem NP-zupełny można przekształcić do naszego problemu zwiększajac trudność problemu co najwyżej wielomianowo. Na pierwszy rzut oka próbowałbym redukcji z problemu IndependentSet.
Problem IndependentSet to pytanie: "czy dla danego grafu G oraz pewnej liczby naturalnej K istnieje podzbiór K wierzchołków z których żadne 2 nie są połączone"
Myślę że możemy w czasie O(n^2) dokonać redukcji IndependentSet do naszego problemu wyjściowego. Jak? Nie będę ci psuł zabawy, bo chyba i tak już za dużo powiedziałem...
twoja odpowiedź, mam nadzieje, że przybliżyła mnie do wyniku, z pewnych notatek wywnioskowalem ze musze udowodnic ze 3coloring nalezy do NP a potem ze 3sat zawiera sie w 3coloring
rozumiem wiec ze 3coloring rozwiazuje ten problem, tylko w jaki sposób można to udowodnić i w jakim celu dokonywac tego kroku z 3sat
To o czym mówisz to 2 krok o ktorym pisałem. Zasadniczo twój problem to jest problem 3-coloring, czyli szczególny przypadek wierzchołkowego k-kolorowania grafu. Problem k-coloring jest problemem NP-zupełnym, więc twój problem też takim problemem jest. Ale domyślam się że nie miałeś podanego w wykładzie dowodu na NP-zupełność k-kolorowania i w efekcie masz je udowodnić. A ten problem akurat najprościej zredukować właśnie z 3CNF-SAT.
W efekcie masz w takim razie udowodnić że problem 3CNF-SAT można przedstawić w postaci problemu 3-coloring.
I nie żadne "zawiera się" tylko redukuję się. Warto przynajmniej rozumieć oznaczenia...