Zeigen Sie, dass die folgende Sprache NP-vollständig ist: HALF-CLIQUE :={G | G ist ein ungerichteter Graph

Question

Hallo an alle. Ich bräuchte Hilfe bei dieser Aufgabe. Wäre jemand so nett mir zu einem Ansatz oder einer Lösung zu verhelfen?



Zeigen Sie, dass die folgende Sprache NP-vollständig ist:

HALF-CLIQUE :={G | G ist ein ungerichteter Graph, |V | ist gerade und G besitzt eine Clique der Größe |V |/2}

Answer 1

Um zu zeigen dass die Sprache NP-vollständig ist, musst du zeigen dass sie NP ist und dann musst du eine andere Sprache, die du weisst dass sie NP-vollständig ist, auf der Sprache HALF-CLIQUE reduzieren. Über welche Sprachen weisst du dass sie NP-vollständig sind?