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$

Jeśli jest wykresem, ile istnieje podzbiorów V o rozmiarze 5 ?$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$