Ich habe ein kleineres Problem aus der theoretischen Informatik.
Für Probleme aus P und NP gibt es ja das Charakteristikum „in Polynomialzeit lösbar“. Mein Problem ist genau dieser Begriff.Mir ist vollkommen unklar in welchen Zusammenhang die länge der codierung und die Polynomialzeit liegen die zur Lösung benötigt wird.
Wenn mir jemand helfen kann ,wäre das klasse,es steht nämlich eine Zwischenprüfung an!
Mathes
Hi.
Du hast einen Algorithmus, der auf einer Eingabe der Laenge n arbeitet (z.B. sollen n Elemente sortiert werden). Wenn du die Zeit, die der Algorithmus benoetigt, (also die Anzahl der Befehle) betrachtest, kannst du diese als Funktion von n angeben, z.B. T(n)=n^5+6n^2+e^n+5. Polynomialzeit bedeutet, dass diese Laufzeitfunktion durch ein Polynom nach oben begrenzt ist. Das oben genannte Beispiel ist also nicht polynomiell, da der Summand e^n sich nicht durch ein Polynom beschraenken laesst. Wenn dir die O-Notation was sagt, kann man das auch so ausdruecken, das Polynomialzeit sich durch O(n^a) angeben laesst, mit a beliebig, aber konstant.
Ich hoffe, das hilft dir weiter,
CU,
Sebastian.
Das heisst also,das z.B. PRIMZAHL deswegen aus NP ist,da sich die Bearbeitungszeit zur Eingabe exponentiell verhält.Also brauch ich für den Test ob 113 Pz. mit Länge der Codierung 3 unverhältnismäßig ,also exponentiell, lange;auf die Codierung bezogen.
Und wie merkt man sowas beim „Durchschnittsproblem“;gibt es da eine bestimmte Vorgehensweise oder nur den gesunden Menschenverstand?
Auf jeden Fall schon mal Danke.
Mathias
Ich würde sagen, man schaut sich den Algorithmus an und versucht die Laufzeit zu bestimmen. Dann kann man es sehen. Wie man es vorher merken kann, weiss ich nicht genau. Aber da gab es doch noch die NP-vollständigen (hießen die so?) Probleme, auf die man andere NP Probleme zurückführen kann. Wenn man also einen Algorithmus hat, der sich auf den NP-vollständigen zurückführen lässt, ist dieser auch NP. Aber das solltest du vielleicht nochmal genauer nachlesen (z.B. in „Theoretische Informatik“ oder in „Kompendium Theoretische Informatik“ [beide von Ingo Wegener] oder auch in anderen Büchern, aber diese beiden fand ich eigentlich ganz in Ordnung (mag daran liegen, das das der Prof war, der die Vorlesung gehalten hat und sich dabei nach seinen Büchern gerichtet hat, aberman konnte gut danach lernen)).
CU,
Sebastian.
Dann glaub ich hab ich es jetzt,danke.
Ach so,ja die heißen NP-vollständige Probleme
Das heisst also,das z.B. PRIMZAHL deswegen aus NP ist,da sich
die Bearbeitungszeit zur Eingabe exponentiell verhält.
Hallo,
das Problem ist aus NP, da es eine nichtdeterministische
Turing Maschine gibt, die ihn in polynomialer Zeit
löst. Die Frage ob das gleichwertig mit exponentiellen Aufwand
bei einer deterministischen Turing Maschine ist, ist ein/das
offene/s Problem.
Also
brauch ich für den Test ob 113 Pz. mit Länge der Codierung 3
unverhältnismäßig ,also exponentiell, lange;auf die Codierung
bezogen.
Vermutlich ja.
Und wie merkt man sowas beim „Durchschnittsproblem“;gibt es da
eine bestimmte Vorgehensweise oder nur den gesunden
Menschenverstand?
Um zu zeigen, daß ein Problem NP-vollständig ist, zeigst Du
zuerst, daß es in NP ist, dann das sich ein wohlbekanntes
NP-vollständiges Problem mit polynomialen Aufwand auf dieses
Problem reduzieren läßt. Die Liste der bekannten NP-vollstän-
digen Probleme ist mittlerweise schon ziemlich umfangreich,
mit ein bisschen Glück findet sich recht bald ein ähnlich
geartetes Problem.
Gruss
Enno