Beantwortet: b) müsste es hier in der Lösung nicht heißse, dass INDSET NP-vollständig ist?

Sat, 06 Jan 2018 17:04:54 +0000

Nein, denn in der Argumentation unter (b, 2) ist nur die NP-Schwere gezeigt worden. Zusammen mit (b, 1) gilt aber auch die NP-Vollständigkeit, da haben Sie recht.

Beantwortet: Allgemeine Fragen

Mon, 08 Feb 2016 19:11:22 +0000

Hallo,

also, der Reihe nach zu deinen Fragen:

1) Die Frage ist erstmal recht allgemein und es sei dir gesagt, dass O(n^2) KEIN linearer Aufwand ist, sondern quadratischer. Linear wäre O(n). Leider gibt es kein eindeutiges "Rezept", um den Aufwand zu erkennen. Daher mal zwei Beispiele, aus denen sich das Erschließen des Aufwands eventuell ergibt:

a) Angenommen, du hast ein Programm, bestehend aus einer Schleife. Diese Schleife wird n-mal durchlaufen, n ist dabei beispielsweise eine Eingabe. Der Berechnungsaufwand steigt also linear mit n an, der Aufwand wäre also O(n).

b) Du möchtest eine Wahrheitstabelle mit Binärvariablen aufstellen. Du hast zunächst zwei Variablen, daher musst du 2^2=4 Kombinationen betrachten. Bei drei Variablen sind es bereits 2^3=8, bei vier Variablen 2^4=16... Der Aufwand (sprich: die Anzahl der Kombinationen) steigt mit jeder Variable um den Faktor 2 an, ist also 2^n für n Variablen. Der Aufwand ist also O(2^n), also exponentiell.

Ich weiß, dass das keine allgemeinen Regeln oder Ähnliches sind, aber eventuell können dir die Beispiele helfen, den Zusammenhang zwischen der Anwendung und der dahinterstehenden Komplexität zu verstehen.

2) Polynome sind alle Funktionen der Form ax^n + bx^(n-1) + ... + ..x^0, also beispielsweise quadratische oder kubische Funktionen aus der Schule. "Polynomialzeit reduzierbar" heißt nun, dass ein Problem in einem Aufwand, der dem Grad eines solchen Polynoms entspricht, umgewandelt werden kann. Am einfachsten ist, sich andere Fälle wie beispielsweise Exponentialzeit als Gegenbeispiel vorzustellen. Der Polynomialzeit kommt besondere Bedeutung zu, weil sie für uns das "noch gut berechenbare" darstellt. Bei bspw. exponentiellem Aufwand wächst die Berechnungsdauer einfach zu schnell zu stark an.

Also: Wenn ein Problem in Polynomialzeit auf ein anderes reduziert werden kann (was sich beispielsweise lohnt, weil wir für dieses andere Problem schon ein Lösungsverfahren haben), dann heißt es "polynomialzeit-reduzierbar".

3) Die Antwort auf die Frage nach einer allg. Lösung ist dieselbe wie in 1).

Zum Beispiel: In KNF sehen Terme ja bspw. so aus: (a ODER b) UND (c ODER d). Will man das jetzt in DNF umwandeln, also mit einem ODER zwischen den Klauseln, so muss man ja die Terme (a UND c), (a UND d), (b UND c) und (b UND d) betrachten. Jetzt war das hier bei zwei Klauseln mit je zwei Variablen noch sehr schön übersichtlich. Hat man aber längere Terme, z.B. (x1 ODER y1) UND (x2 ODER y2) UND (x3 ODER y3), dann wird die Umwandlung schon deutlich länger. Auch hier ist der Aufwand exponentiell.

So, lange Rede kurzer Sinn: Es gibt hier kein Patentrezept, daher Unterlagen anschauen, verschiedene Aufgaben machen und ein Gefühl dafür bekommen. Ich hoffe einfach mal, dass meine obigen Beispiele ein bisschen dieses Gefühl getroffen haben.

Viele Grüße

Max (Tutor)

Beantwortet: Tutorium 4 Aufgabe 2

Tue, 29 Dec 2015 10:45:30 +0000

Hey,

der Aufgabenstellung kannst du entnehmen, dass SAT polynomialzeit-reduzierbar auf CLIQUE ist. Nicht angegeben, aber vorausgesetzt ist das Wissen, dass SAT ein NP-vollständiges Problem ist und somit in NP liegt.

Definition NP-schwer:
Ein Problem X ist genau dann NP-schwer, wenn jedes anderes Problem, welches in NP liegt, auf X polynomialzeit-reduzierbar ist.

Und genau das liegt hier vor: SAT liegt in NP und ist auf CLIQUE polynomialzeit-reduzierbar, somit ist CLIQUE ein NP-schweres Problem. (Tutorium 4 Folie 9 zeigt eine analoge Multiple-Choice Frage).

Daher muss nur noch gezeigt werden, dass CLIQUE in NP liegt, um die NP-Vollständigkeit zu zeigen.

Viele Grüße
Ashvin (Tutor)

Beantwortet: Was genau ist ein Clique ?

Tue, 22 Sep 2015 09:58:22 +0000

Hallo,

Clique bezeichnet einen Teilgraphen, bei dem alle Konten zu jedem anderen Knoten aus dem Teilgraphen verbunden sind.

Gruß

Marcel (Tutor)

Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in HU-4-1

Beantwortet: b) müsste es hier in der Lösung nicht heißse, dass INDSET NP-vollständig ist?

Beantwortet: Allgemeine Fragen

Beantwortet: Tutorium 4 Aufgabe 2

Beantwortet: Was genau ist ein Clique ?