HALF CLIQUE - NP Schließe das Problem ab

Lassen Sie mich mit der Feststellung beginnen, dass dies ein Problem bei den Hausaufgaben ist. Bitte geben Sie nur Ratschläge und entsprechende Beobachtungen, KEINE DIREKTEN ANTWORTEN, bitte . Nachdem dies gesagt wurde, ist hier das Problem, das ich betrachte:

Sei HALF-CLIQUE = { | ist ein ungerichteter Graph mit einem vollständigen Untergraphen mit mindestens Knoten, wobei n die Anzahl der Knoten in } ist. Zeigen Sie, dass HALF-CLIQUE NP-vollständig ist.$\langle G \rangle$$G$$n/2$$G$

Außerdem kenne ich folgendes:

• In Bezug auf dieses Problem wird eine Clique als ungerichteter Untergraph des Eingabegraphen definiert, bei dem jeweils zwei Knoten durch eine Kante verbunden sind. Eine Clique ist eine Clique, die Knoten enthält .$k$$k$
• Nach unserem Lehrbuch, Michael Sipsers " Introduction to the Theory of Computation ", S. 268, ist das Problem CLIQUE = { | ist ein ungerichteter Graph mit einer Klasse} ist in NP$\langle G,k\rangle$$G$$k$
• Darüber hinaus stellt CLIQUE laut derselben Quelle (auf S. 283) in NP-Complpete (also offensichtlich auch in NP) fest.

Ich glaube, ich habe hier den Kern einer Antwort, aber ich könnte einen Hinweis darauf gebrauchen , was daran falsch ist, oder irgendwelche verwandten Punkte, die für eine Antwort relevant sein könnten . Dies ist die allgemeine Idee, die ich bisher habe,

Ok, ich würde zuerst bemerken, dass ein Zertifikat einfach eine HÄLFTE von . Nun scheint es, dass ich einen Verifizierer erstellen müsste, der eine polynomielle Zeitverringerung von CLIQUE (von dem wir wissen, dass es NP-Complete ist) zu HALF-CLIQUE darstellt. Meine Idee wäre, dass dies durch die Erstellung einer Turing-Maschine geschehen würde, auf der der Turing-Maschinenprüfer im Buch für CLIQUE mit der zusätzlichen Einschränkung für HALF-CLIQUE ausgeführt wird.$\text{size} \geq n/2$

Das hört sich für mich richtig an, aber ich vertraue mir in diesem Bereich noch nicht wirklich. Ich möchte noch einmal daran erinnern, dass dies ein HAUSHALTSPROBLEM ist. Versuchen Sie daher, die Beantwortung der Frage zu vermeiden. Jede Anleitung, die dies nicht erfüllt, wäre sehr willkommen!

Gemessen an Ihrer Beschreibung und Ihren Kommentaren hilft Ihnen möglicherweise eine genaue Beschreibung, wie Reduktionen zum Nachweis der NP-Vollständigkeit verwendet werden können, am besten:

Ein Problem ist NP-vollständig, wenn es sich um NP handelt und NP-schwer ist. Dies bedeutet, dass jeder Nachweis der NP-Vollständigkeit aus zwei Teilen besteht: einem Beweis, dass das Problem in NP liegt, und einem Beweis, dass es NP-schwer ist.

Im ersten Teil muss gezeigt werden, dass JA-Instanzen mit einem geeigneten Zertifikat in polynomialer Zeit verifiziert werden können. Alternativ können Sie zeigen, dass das Problem durch eine nicht deterministische Turing-Maschine in polynomialer Zeit gelöst werden kann, aber dies wird normalerweise nicht getan, da Fehler leicht gemacht werden können.

In Ihrem Fall kommt es darauf an, zu beweisen, dass Sie für jeden Graphen mit einer Klasse einen Beweis finden, dass es tatsächlich eine solche Klasse gibt, sodass Sie mit einem solchen Beweis bewaffnet die polynomielle Zeit einchecken können Es gibt in der Tat eine solche Clique.$n/2$

Im zweiten Teil muss gezeigt werden, dass das Problem NP-schwer ist. Dies wird in fast allen Fällen durch den Nachweis gezeigt, dass Ihr Problem mindestens so schwer wie ein anderes NP-hartes Problem ist. Wenn HALF-CLIQUE mindestens so hart ist wie CLIQUE, muss es auch NP-hart sein.

Sie tun dies durch eine Reduzierung beweisen VON Clique, ZU HALB CLIQUE. Sie reduzieren das Problem und machen es einfacher. Sie sagen, "CLIQUE zu lösen ist schwierig, aber ich habe bewiesen, dass Sie nur HALB-CLIQUE lösen müssen, um CLIQUE zu lösen". (Viele Leute, sogar Experten, sagen dies gelegentlich falsch herum :))

Es gibt verschiedene Arten von Reduktionen: Die am häufigsten verwendete Reduktion ist die, bei der Sie Instanzen von CLIQUE in diesem Fall Instanzen von HALF-CLIQUE zuordnen, deren Größe in Polynomzeit höchstens polynomiell größer ist. Dies bedeutet, dass wir, wenn wir HALF-CLIQUE lösen können, auch CLIQUE lösen können, indem wir den Algorithmus und die Reduktion verketten.

Mit anderen Worten, wir müssen zeigen, dass wir CLIQUE lösen können, wenn wir HALF-CLIQUE lösen können. Wir tun dies, indem wir zeigen, dass wir für jede Instanz von CLIQUE eine Instanz von HALF-CLIQUE so entwerfen können, dass die Instanz von CLIQUE eine 'Ja'-Instanz ist, wenn die Instanz von HALF-CLIQUE eine' Ja'-Instanz ist.

Der Beweis fängt also so an: Mit einem Graphen kann ich einen Graphen H = ( V ′ , E ′ ) erzeugen , so dass G eine k- Klasse enthält, wenn H eine n / 2- Klasse enthält. Ich überlasse diesen Teil Ihnen (dies ist der Teil, der Kreativität erfordert, der Teil, der sich mit dem jeweiligen Problem befasst).$G=(V, E)$$H=(V', E')$$G$$k$$H$$n/2$

$\ge$

$G$$k$$H$$H$$G$$k$

Der unten stehende Spoiler enthält einen Hinweis zur Durchführung dieser Reduzierung:

$H$$G$

Sie können das Vertex-Cover-Problem reduzieren. Wenn das Komplementdiagramm des angegebenen Diagramms eine Scheitelpunktabdeckung von weniger als n / 2 Knoten aufweist, weist dieses Diagramm eine Clique von mehr als n / 2 Knoten auf, dh, es handelt sich um eine halbe Clique. Geben Sie einfach an, dass es schwierig ist, das Vertex Cover-Problem zu lösen.