+1 Daumen
816 Aufrufe
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}
Avatar von

1 Antwort

0 Daumen

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?

Avatar von 6,9 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community