Die Klasse NP
-
Hallo allerseits. Ich bin neu hier
Folgende Aufgabe bereitet mir Problem, auch wenn ichglaube sie ist eigentlich nicht so schwer.
(a) Geben sie eine Sprache aus NP an. Begründen sie ihre Antwort.
-> ich habe allgemein etwas Probleme mit dem Begriff NP. Google spuckt nur Sachen aus wie "entscheiden ob ein Graph einen Hamilton-Kreis hat" oder sowas...heisst es dann die Sprache, welche entscheidet ob ein Graph einen Hamilton-Kreis hat, liegt in NP? Inwiefern müsste ich die Antwort dann begründen?
*
(b) Beweisen, dass NP unter Schnitt abgeschlossen ist.
*
-> kann ich hier nicht einfach schreiben wir haben eine NTM1 und NTM2 für L1 und L2, diese schalten wir hintereinander und akzeptieren nur wenn beide akzeptieren? Dann habe ich doch eine NTM mit polynomieller Laufzeit O(2n^a) wobei O(n^a) die größere Laufzeit der beiden NTMs ist?Vielen Dank schonmal. Kann gut sein dass ich mit noch mehr Fragen auftauche
-
b) ist IMHO richtig. Bei a) solltest du dich nochmal informieren, was eine Sprache ist. Wenn du schreibst "Sprache, die entscheidet ob..." scheinst du da noch wesentliche Defizite zu haben.
-
Also eine Sprache haben wir als Menge von Wörtern definiert. Über diese Wörter versuchen wir dann Probleme (meist ja/nein) zu kodieren. Dann entscheiden wir ob das Wort aus der Sprache ist (->dann "ja") oder nicht ("nein").
Bzgl. des Hamilton-Kreises würde L dann ähnlich folgendermassen aussehn:
- *g1..gn = Knoten des Graphen
- L=(w | w ist Permutation von g1..gn, wobei Kanten existieren zw. w1 und w2, w2 und w3, ..., wn-1 und wn)
Richtig? Wie würde ich das mit den Kanten kodieren?
-
ich habe allgemein etwas Probleme mit dem Begriff NP.
Nun, darüber gibt es genug im Netz. Es ist die Klasse der Sprachen die in Polynomialzeit verifizierbar sind.
Also eine Sprache haben wir als Menge von Wörtern definiert. Über diese Wörter versuchen wir dann Probleme (meist ja/nein) zu kodieren. Dann entscheiden wir ob das Wort aus der Sprache ist (->dann "ja") oder nicht ("nein").
Jo, alles richtig.
Edit: Moment - über die Wörter versuchst du Probleme zu kodieren? Klingt irgendwie merkwürdig. Sag das nochmal klarer.Richtig?
Sollte die Sprache nicht die (kodierten) Graphen enthalten? Außerdem enthält der Hamilton-Kreis nicht zwangsläufig alle Knoten...
Wie würde ich das mit den Kanten kodieren?
Als Adjazenzmatrix in eindimensionaler Form, wäre so meine Idee.
O(2n^a)
Ist dasselbe wie O(n^a). In der Big-O-Notation ist doch eine Konstante versteckt.
-
Die Definition von NP habe ich wohl gefunden, aber für mich hört sich das irgendwie sehr abstrakt an.
Das Kodieren der Probleme über Wörter meine ich zB so: Wir wollen gucken ob die Länge eines Wortes gerade oder ungerade ist. Die Sprache hierzu ist dann L={w||w|=2x, x aus N}.
Was ist denn nun zum Beispiel ein einfaches (das einfachste?) Beispiel für eine Sprache aus NP? Vielleicht erhellt mich das ja schon.
Achso und natürlich schonmal ein dickes Dankeschön für die bisherige Hilfe.
-
.chicken schrieb:
Was ist denn nun zum Beispiel ein einfaches (das einfachste?) Beispiel für eine Sprache aus NP? Vielleicht erhellt mich das ja schon.
Was ist denn überhaupt die einfachste Sprache, die dir direkt einfällt. Vielleicht ist die ja schon in NP...
-
Alle Wörter über dem Alphabet {a}....die sollte natürlich in polynomieller Zeit verifizierbar sein, aber kann die Aufgabe wirklich so einfach sein?
-
Das ist halt eine einfache Verständnisaufgabe.
-
Wie wäre es mit dem Faktorisierungsproblem?
Die Sprache hierzu ist dann L={w||w|=2x, x aus N}.
Geht viel einfacher:
Edit: Ist dir Klar, das jede Sprache in P auch in NP ist ( )? Sicher, dass sie nicht NP-vollständige Probleme wollen?
Edit²: Ups, falsch herum notiert
-
Arcoth schrieb:
Die Sprache hierzu ist dann L={w||w|=2x, x aus N}.
Geht viel einfacher:
Das ist kürzer aber nicht einfacher. Die Schreibweise von chicken findet man so in jedem Lehrbuch und es gibt keine Fleißpunkte für die kürzeste Syntax.
-
Ok, danke für die vielen Antworten. Dann werde ich das morgen so abgeben
-
Arcoth schrieb:
Sollte die Sprache nicht die (kodierten) Graphen enthalten? Außerdem enthält der Hamilton-Kreis nicht zwangsläufig alle Knoten...
Doch, ein Hamilton-Kreis enthält per Definition alle Knoten. Und die Sprache soll natürlich nur diejenigen Wörter enthalten, die einen hamiltonschen Graphen kodieren, nicht alle kodierten Graphen.
-
Und die Sprache soll natürlich nur diejenigen Wörter enthalten, die einen hamiltonschen Graphen kodieren, nicht alle kodierten Graphen.
*facepalm* Das ist mir klar. Genau das meinte ich auch. Ich schrieb ja auch "die kodierten" und nicht "alle kodierten"...
Doch, ein Hamilton-Kreis enthält per Definition alle Knoten.
Oh, stimmt.
