Np	Neue Frage »

06.02.2009, 19:05	Nagato	Auf diesen Beitrag antworten »
Np Hallo, bei de.wikipedia.org/wiki/NP_(Komplexit%C3%A4tsklasse) bin ich auf die Suchproblem-Definition für NP gestoßen. Ich verstehe die Definition überhaupt nicht. Es wäre nett wenn jemand mir das erklären könnte. vieleicht auch noch was genau ein Suchproblem ist. Daraus werde ich auch nicht schlau. schonmal vielen dank für eure Hilfe
06.02.2009, 20:18	kiste	Auf diesen Beitrag antworten »
Hallo, wo genau liegt den das Problem? Warum das Suchproblem-Definition heißt weiß ich nicht, aber der Beweis der Äquivalenz zur "üblichen" Definition ist doch aufschlussreich? Gruß PS: Naruto-Fan?
06.02.2009, 20:33	Nagato	Auf diesen Beitrag antworten »
Für mich irgenwie nicht. Wrum steht zb da $\begin{eqnarray} \|y\| \leq p(\|x\|) \end{eqnarray}$ oder was ist mit $\begin{eqnarray} (x,y) \in R_L \end{eqnarray}$ gemeint das Tupel sollte dann (0,0),(1,0),(0,1),(1,1) sein aber was bedeutes das?
06.02.2009, 20:42	kiste	Auf diesen Beitrag antworten »
Nein es ist auch möglich dass (11101,100001111) in der Relation ist. * bedeutet beliebig viele Aneinanderreihungen der Symbole. Aber solangsam glaube ich auch dass die Definition falsch ist da R_L meiner Meinung nach von einer TM in P erkannt werden muss
06.02.2009, 20:50	Nagato	Auf diesen Beitrag antworten »
aber RL wird soll doch von einer deterministischen Turingmaschine erkannt werden aber mir ist garnicht klar was $\begin{eqnarray} (x,y) \in R_L \end{eqnarray}$ bedeuten soll und warum man $\begin{eqnarray} \|y\| \leq p(\|x\|) \end{eqnarray}$ fordert
06.02.2009, 20:53	kiste	Auf diesen Beitrag antworten »
Das erste bedeutet dass x und y in Relation zueinander stehen. Das zweite benötigt man da sonst alleine das Raten der Eingabe länger als polynomielle Zeit benötigt
Anzeige

06.02.2009, 21:13	Nagato	Auf diesen Beitrag antworten »
$\begin{eqnarray} \|y\| \leq p(\|x\|) \end{eqnarray}$ bedeutet doch nur das die länge des wortes $\begin{eqnarray} \|y\| \end{eqnarray}$ kleiner ist als $\begin{eqnarray} p(\|x\|) \end{eqnarray}$ aber wenn jetzt gelten würde $\begin{eqnarray} p(\|x\|)\leq \|y\| \end{eqnarray}$ dann heist das doch nicht das ich es nicht in polynomieller Zeit schaffe? bzw wahrscheinlich schon aber ich verstehe es nicht. $\begin{eqnarray} (x,y) \in R_L \in P \end{eqnarray}$ heist das dann das ich entscheiden kann (in polynomieller Zeit) ob x und y in relation zueinander stehn?
06.02.2009, 21:24	kiste	Auf diesen Beitrag antworten »
Nein man kann es trotzdem noch schaffen, aber es ist einfach nicht mehr sichergestellt. Gibt es ein p mit $\begin{eqnarray} p(\|x\|) \leq \|y\| \end{eqnarray}$ so kann es immer noch p' geben mit $\begin{eqnarray} \|y\| \leq p'(\|x\|) \end{eqnarray}$ . Beim zweiten stimme ich dir zu
06.02.2009, 21:45	Nagato	Auf diesen Beitrag antworten »
Ich verstehe das jetzt so: salop gesagt ist L das "Problem" und x eine Lösung. Stimmt das? $\begin{eqnarray} L \in NP \end{eqnarray}$ d.h ich brauche höchstens $\begin{eqnarray} p(\|x\|) \end{eqnarray}$ "Zeit" um zu entscheiden ob $\begin{eqnarray} x \in L \end{eqnarray}$ daraus folgt jetzt aber es gibt eine andere Lösung y die für die gilt $\begin{eqnarray} \|y\| \leq p(\|x\|) \end{eqnarray}$ : also für die ich höchstens solange brauche zu entscheiden ob es eine Lösung in L ist wie für x. und zusätzlich müssen (x,y) in Relation stehn. Aber was bedeutet hier genau in Realtion stehn?
07.02.2009, 13:54	Nagato	Auf diesen Beitrag antworten »
Vieleicht könnte man das dann auchmal an einem Beispiel erklären: Ich hab zb. $\begin{eqnarray} z1...zn \end{eqnarray}$ eine menge aus n natürlichen Zahlen. Deren Summe S der Zhalen sei gerade. Jetzt ist die Frage ob es eine Teilmenge gibt deren Summe S/2 ist. Was wäre in der Aufgabe x,L,y und RL?
07.02.2009, 14:25	kiste	Auf diesen Beitrag antworten »
x ist die Eingabe $\begin{eqnarray} z_1\ldots z_n \end{eqnarray}$ . y ist die Folge der Teilindizes die genau S/2 ergibt. L ist die Sprache jener $\begin{eqnarray} z_1\ldots z_n \end{eqnarray}$ die eine solche Teilfolge besitzen und R_L ist die Relation die die Eingabe mit ihrer Lösung in Relation stellt.
07.02.2009, 14:37	Nagato	Auf diesen Beitrag antworten »
also steh x und y in realtion zueinander wenn y eine Teilmege von x ist so das die summe der zi in y S/2 ergeben? und warum muss dann in dem konkreten beispiel $\begin{eqnarray} \|y\| \leq p(\|x\|) \end{eqnarray}$ gelten wnnd als \|y\| nicht polynomiell ist würde ich dann um y zu verifizieren länger als polynomielle Zeit benötigt?
07.02.2009, 14:39	kiste	Auf diesen Beitrag antworten »
Alleine das Raten würde länger als polynomielle Zeit brauchen aber natürlich auch das Überprüfen den dafür muss ja mindestens y einmal gelesen werden.
07.02.2009, 14:46	Nagato	Auf diesen Beitrag antworten »
1. also steh x und y in realtion zueinander wenn y eine Teilmege von x ist so das die summe der zi in y S/2 ergeben? 2. Ich versteh nich warum das Raten länger als polynomielle Zeit brauch. Was wäre denn die Eingabe dafür? \|x\|?
07.02.2009, 14:50	kiste	Auf diesen Beitrag antworten »
Wenn ich etwas nicht kommentiere ist es meist richtig 1. stimmt also bei der konkreten Sprache 2. Raten beinhaltet hinschreiben, wenn y nicht-poly länge hat dauert das eben länger als poly-zeit Die Eingabe wofür? Es gibt eigentlich nur eine Eingabe und die ist eben x.
07.02.2009, 14:56	Nagato	Auf diesen Beitrag antworten »
Ich meine: wenn ich y hinschreibe hängt das hinschreiben von y ja linear von \|y\| ab. aber zb wenn gilt \|y\|=2^\|x\| exp von \|x\|. Sagen wir ich brauche 1 Rechneschritt um ein Zeichen hinzuschreiben. also bracuh ich für jedes y nur \|y\| Zeit ist ja mal egal wie groß die ist.
07.02.2009, 15:11	kiste	Auf diesen Beitrag antworten »
\|x\| ist aber die Größe in der es polynomiell sein muss!
07.02.2009, 15:15	Nagato	Auf diesen Beitrag antworten »
Vielen Dank! Dank deiner Hilfe habe ich es Verstanden! (denke ich)
07.02.2009, 15:20	kiste	Auf diesen Beitrag antworten »
Ich danke auch, jetzt kenne ich eine neue Definition

Neue Frage »

Antworten »

Np

Verwandte Themen