Finden eines 5-Punkt-Sterns in Polynomzeit

Ich möchte feststellen, dass dies Teil meiner Hausaufgaben für einen Kurs ist, den ich gerade besuche. Ich bin auf der Suche nach Hilfe, keine Antwort.

Dies ist die fragliche Frage:

Ein 5-Stern in einem ungerichteten Diagramm ist eine 5-Clique. Zeigen Sie diesen 5-PUNKT-STERN , wobei 5-PUNKT-STERN = einen 5- Punkt -Stern als Untergraph .$\in P$$\{ <G>$ $: G$$\}$

Wobei eine Clique CLIQUE = ist ein ungerichteter Graph mit einer Clique .$\{(G, k) : G$$G$$k$$\}$

Mein Problem ist nun, dass dies das CLIQUE-Problem zu lösen scheint, indem bestimmt wird, ob ein Diagramm eine Clique enthält, mit der zusätzlichen Einschränkung zu bestimmen, dass die CLIQUE einen fünfzackigen Stern bildet. Dies scheint eine geometrische Berechnung zu beinhalten, die auf der Kenntnis eines fünfzackigen Sterns beruht . In Michael Sipsers Theory of Computation , S. 268, gibt es jedoch einen Beweis dafür, dass CLIQUE in und auf Seite 270 wird darauf hingewiesen, dass$NP$

Wir haben Beispiele für Sprachen wie HAMPATH und CLIQUE vorgestellt, die Mitglieder von NP sind, von denen jedoch nicht bekannt ist, dass sie in . $P$[Betonung hinzugefügt]

Wenn CLIQUE nicht in , warum sind fünf Sternchen in ? Gibt es etwas, das ich nicht sehe? Denken Sie daran, dies ist ein HAUSARBEITSPROBLEM und eine direkte Antwort wäre nicht wertzuschätzen. Vielen Dank!$P$$P$

Wenn ein Graph ist, wie viele Teilmengen von der Größe existieren?$G=(V,E)$$V$$5$

Wenn es eine 5-Clique gibt, ist eine dieser Teilmengen eine Clique.

Spoiler unten:

Es gibt mögliche Teilmengen, die geprüft werden sollen, d. h. höchstens Optionen, die in der Eingabe polynomisch sind. Dies ist für ein beliebiges NICHT der Fall , da in der Eingabe exponentiell sein kann, und aus diesem Grund (außer P = NP, agghh.).${|V| \choose 5}$$|V|^5$$k$$|V|^k$$\text{CLIQUE} \notin P$