Znalezienie gwiazdy 5-punktowej w czasie wielomianowym

Chcę ustalić, że jest to część mojej pracy domowej na kursie, który obecnie biorę. Szukam pomocy w postępowaniu, NIE ODPOWIEDZI.

Oto pytanie:

Gwiazda pięcioramienna na niekierowanym wykresie jest pięcioklasową. Pokaż, że 5-POINTED-STAR , gdzie 5-POINTED-STAR = zawiera gwiazdę 5-punktową jako podgraf . $\in P$ $\{ <G>$ $: G$ $\}$

Gdzie klika to CLIQUE = jest niekierowanym wykresem z kliką . $\{(G, k) : G$ $G$ $k$ $\}$

Teraz moim problemem jest to, że wydaje się, że rozwiązuje to problem CLIQUE, określając, czy wykres zawiera klikę z dodatkowym ograniczeniem konieczności ustalenia, że CLIQUE tworzy gwiazdę 5-punktową. Wydaje się, że wiąże się to z pewnymi geometrycznymi obliczeniami opartymi na wiedzy o gwiazdach pięcioramiennych . Jednak w teorii obliczeń Michaela Sipsera , str. 268, istnieje dowód na to, że CLIQUE jest w a na stronie 270 zauważa, że: $NP$

Przedstawiliśmy przykłady języków, takich jak HAMPATH i kliki, które są członkami NP ale które nie są znane być w . $P$ [podkreślenie dodane]

Jeśli CLIQUE nie jest w , dlaczego pięcioramienna gwiazda ma być w ? Czy jest coś, czego nie widzę? Pamiętaj, że jest to PROBLEM Z PRACĄ DOMOWĄ, A BEZPOŚREDNIA ODPOWIEDŹ NIE BĘDZIE WYRAŻONA. Dzięki! $P$ $P$

complexity-theory time-complexity

— BrotherJack
źródło

Jeśli jest wykresem, ile istnieje podzbiorów o rozmiarze ? $G=(V,E)$ $V$ $5$

Jeśli występuje klika 5, jednym z tych podzbiorów jest klika.

Spojlery poniżej:

Istnieją możliwych podzbiorów do sprawdzenia, czyli co najwyżej opcje , które są wielomianem na wejściu. Nie jest tak w przypadku dowolnego , ponieważ może być wykładniczy na wejściu, i dlatego (chyba że P = NP, agghh.). ${|V| \choose 5}$ $|V|^5$ $k$ $|V|^k$ $\text{CLIQUE} \notin P$

— Ran G.
źródło

Myślę, że to mnie denerwuje. Miałem wrażenie, że problem CLIQUE został sformułowany w ten sposób, aby po prostu oznaczać, że można go zastosować do dowolnej kliki o rozmiarze, i że rozmiar ten podano jako część problemu. Podczas gdy w tym problemie wydaje się, że rozmiar CLIQUE jest nieznany (jeszcze w tym przypadku jest to 5). Teraz, gdybym miał zbudować deterministyczną maszynę Turinga z pojedynczą taśmą, która zdecydowałaby się rozwiązać ten problem w czasie wielomianowym, to stanowiłaby odpowiedź (biorąc pod uwagę, że dowód jest solidny), tak?

— BrotherJack

P

$P$

Interesujące może być powiązanie tego efektu ze sparametryzowaną złożonością .

— Raphael

Nie wiedziałem, że możesz zrobić efekt spoilerów. Dobra wskazówka.

— Joe