Die Klasse NP

[Columbo]

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.

[.chicken]

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.

[Bashar]

.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...

[.chicken]

Alle Wörter über dem Alphabet {a}....die sollte natürlich in polynomieller Zeit verifizierbar sein, aber kann die Aufgabe wirklich so einfach sein?

[Bashar]

Das ist halt eine einfache Verständnisaufgabe.

[Columbo]

Wie wäre es mit dem Faktorisierungsproblem?

Die Sprache hierzu ist dann L={w||w|=2x, x aus N}.

Geht viel einfacher:
$L = \{ *^{2t} \}$

Edit: Ist dir Klar, das jede Sprache in P auch in NP ist ($\mathbf{P} \subseteq \mathbf{NP}$ )? Sicher, dass sie nicht NP-vollständige Probleme wollen?
Edit²: Ups, falsch herum notiert

[qweasdyxc]

Arcoth schrieb:

Die Sprache hierzu ist dann L={w||w|=2x, x aus N}.

Geht viel einfacher:
$L = \{ *^{2t} \}$

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.

[.chicken]

Ok, danke für die vielen Antworten. Dann werde ich das morgen so abgeben

[Jester]

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.

[Columbo]

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.