definition von NP bei wikipedia

Neue Frage »

Wolfskehl Auf diesen Beitrag antworten »
definition von NP bei wikipedia
moin, ich hoffe ich bin hier richtig, und zwar mit einer anmerkung zu der definition der klasse NP bei wikipedia:

http://www.matheboard.de/lexikon/index.php/NP_(Komplexit%E4tsklasse)

dort heißt es:
Häufig wird NP irrtümlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Dies ist aber falsch, da die Menge der in Polynomialzeit lösbaren Probleme eine (vermutlich echte) Teilmenge von NP ist.

IMHO gibt es noch eine zweite begründung dafür, dass es sich um einen irrtum handelt. die 'nicht in polynomzeit lösbaren probleme' beinhalten ja auch solche, die z.b. die komplexität O(n^(n^(n^n))) o.ä. haben oder überhaupt nicht lösbar sind. und die gehören ja nicht zu NP, da sie auch von einer indeterministischen TM nicht in polynominalzeit entschieden werden können.

sieht das hier jemand genauso oder gibt es einwände?

danke

ps: die definition fand ich auf dieser seite, daher dieses forum.
Sir Jective Auf diesen Beitrag antworten »

Hallo,

für Diskussionen zu Wikipedia-Seiten sind eigentlich die zugehörigen Diskussionsseiten da, die aber von diesem Mirror hier (noch) nicht verlinkt sind.

Bitte wiederhole deine Frage auf dieser Seite.

Ich gebe zu, dass ich den von dir zitierten Absatz des Artikels nicht wirklich verstehe; deine Begründung ist dagegen sehr gut verständlich.

Gruss,
SirJective
Wolfskehl Auf diesen Beitrag antworten »

also den absatz kann ich erklären:

P ist die klasse der probleme, die von einer deterministischen touring maschine in polynomineller zeit gelöst werden können. d.h. es gibt ein bestimmtes programm und genau das wird von der touring maschine abgearbeitet. irgendwann kommt dann als antwort ja oder nein raus bzw. das ergebnis. ein 'normales programm' (z.b. c o.ä.) würde dafür ebenfalls polynominelle zeit brauchen, d.h. das n wäre NICHT im exponent. z.b. n^3 oder 52*n^5+89. das P steht in dem fall für -P-olynominell.

tja und NP steht eben (leider) NICHT für -N-icht -P-olynominell, wie viele studenten denken. es bedeutet, dass eine -N-icht deterministische touring maschine das problem in -P-olynomineller zeit lösen kann. eine nicht deterministische touring maschine hat die möglichkeit, zu 'raten' wie sie weiter vorgeht, d.h. welchen befehl sie ausführt.

eine deterministische würde wissen: auf dem band steht eine 1, ich habe einen gewissen zustand und wenn das so ist, dann ersetze ich die 1 durch eine 0, gehe 1 feld nach links und gehe in einen bestimmten andern zustand. eine NICHT deterministische touring maschine hätte mehrere möglichkeiten zur auswahl, was sie machen kann und hier ist 'raten' gleichbedeutend damit, dass sie alle möglichkeiten gleichzeitig ausführt.

beispiel: sie muss einen binären suchbaum durchsuchen, der die höhe 10 hat. die deterministische touring maschine müsste ALLE zweige nacheinander rekursiv absuchen und immer wenn die höhe 1 zunimmt, dann verdoppelt sich die zahl der zu durchsuchenden knoten. bei 10 wären es also 1023 suchen, d.h. 2^10-1.
die nicht deterministische touring maschine hat die möglichkeit, alle äste auf einer höhe GLEICHZEITIG abzusuchen, d.h. in der 1. iteration sucht sie in der wurzel, in der 2. die äste die dort abzweigen, in der 3. wiederum die nächsten äste (4 stück) und damit bräuchte sie nur 10 statt 1023 zeiteinheiten bis sie 'unten angekommen' ist. also n statt 2^n.

probleme, die das n im exponenten haben, gehören also zu NP. und zwar genau dann wenn sie wirklich nur das N da drin haben und nicht 2^n oder so. sie gehören aber auch dann zu NP wenn sie KEIN n im exponent haben, denn wenn eine nicht ratende touring maschine das problem schon in polynomineller zeit lösen kann, dann die ratende erst recht. das war das 1. missverständnis. viele studenten denken NUR die probleme wo das n im exponent ist, gehören zu NP und die wo es nicht dort steht, würden nicht dazu gehören. das ist unsinn. andere denken, nur die probleme, wo das n NICHT in der basis steht, also z.b. n^2 würden dazu gehören. das ist genauso falsch, denn da wären auch die dabei, wo 2^n im exponent steht oder wo es gar keine lösungsmöglichkeit gibt...

hm weiß nicht ob das jetzt verständlich war.... verwirrt
Mazze Auf diesen Beitrag antworten »

Hm , bei uns hamse den Unterschied ganz klar deutlich gemacht. Deswegen bin ich wohl auch nicht auf dein Teile beim wikipedia gestoßen ^^.

Ich habe damals beim simulieren eines Kellerautomatens auch eine NDTM genommen, aber im Gegensatz zu deiner darstellung hab ich nicht "alles gleichzeitig" gemacht, so wie du den baum durchsucht hast, sondern es hat gereicht wenn die turingmaschiene den richtigen pfad rät. Und dann wäre die Baumsuche nicht n sondern sogar log n. Du weißt sicher das man bei NDTMS den Zeitaufwand nach bestcase abschätzt,und bestcaste ist halt dieses "immer richtig raten". Deswegen is log n vollkommen legitim für eine NDTM. Daraus folgt insbesondere das Probleme mit höherrangigen exponent 2^n^n^n^n... im bestcase wohl auch für eine NDTM in polynomieller Zeit machbaren wären. (Das erfordert aber wohl einen recht knackigen beweis denk ich Augenzwinkern )
Im prinziep basiert dieser wohl darauf, das solange ein problem einen pfad hat der in polynomieller Zeit zu lösen ist, solange ist das Problem in NP. Sobald dein Problem eben nicht mehr auf diesen polynomiellen pfad zu reduzieren ist , dann kannst du davon sprechen das es ausserhalb liegt.

Ach ja zum Nichtdeterminismus

Das heißt nicht das eine Maschine x Sachen auf einmal macht, das heißt das eine Maschine für die selbe kannte mehrere unterschiedliche Folgezustände hat. Es kann nur einen geben (muha) der angesteuert wird, wer das is das rätst du.
Wolfskehl Auf diesen Beitrag antworten »

ja ok wenn du die zahl der knoten (also 1023) als n annimmst, dann natürlich log n :-)

raten wäre gleichzusetzen mit alles gleichzeitig zu durchsuchen. wenn wenn du z.b. bei einer iteration 8 äste zur auswahl hast, dann ist es egal ob du in einer ZE den richtigen rätst oder alle gleichzeitig durchprobierst und dann weißt welcher der richtige ist.

wir hatten das beispiel mit dem palindrom. 'die mitte raten' hieß in dem fall, dass die TM bei jeder iteration einmal annimmt die mitte wäre erreicht und einmal dass sie noch nicht erreicht ist und diese 'annahmen' eben auch gleichzeitig trifft bzw. guckt was dann raus käme. jedes mal zwei möglichkeiten zu haben (bis sie dann tatsächlich gefunden wurde) wäre so ähnlich wie das mit dem suchbaum. beide möglichkeiten gleichzeitig.

ich meine mich erinnern zu können dass unsere prof. auch gesagt hat, ein problem der komplexität 2^(2^(2^n))) o.ä. wäre mit einer NDTM nicht in polynomineller zeit zu lösen. aber selbst wenn gibt es da noch die probleme die gar nicht lösbar bzw nicht entscheidbar sind...und die gehören sicher nicht zu NP.


zu deinem ps: wenn du annimmst, dass die NDTM eh nur rein hypothetisch ist und nicht real, dann kannst du auch sagen, zwei unterschiedliche folgezustände werden gleichzeitig abgelaufen. denn würden sie es nicht, wäre es ja nicht indeterministisch oder? wirklich 'raten' kann auch die NDTM nicht. denn raten bedeutet, dass du etwas sagst ohne es zu wissen und es kann richtig oder falsch sein. du kannst aber auch sagen, sie rät alle folgezustände gleichzeitig, hat genau 1 mal richtig gelegen und macht dann damit weiter :-)
Mazze Auf diesen Beitrag antworten »

probleme die nich lösbar/entscheidbar sind liegen mit sicherheit nicht in Np, das folgt schon aus der Definition

NP:

Alle problemklassen die eine NDTM in polynomialer zeit lösen kann. alles klar?

Ach ja wenn 2^2^2^n nicht geht dann wirds da wohl kein Pfad geben der sich auf p(N) reduzieren lässt, für jede eingabe.

wenn ich mich recht endsinne hat auch eine NDTM eine fixe anzahl von zuständen, lässt du die machine in 2 Zustände laufen, als was willst du sie beschreiben? Es wird mehr oder minder ein metazustand erzeugt (x zustände gleichzeitg) der sich wenn überhaupt als nur neuen Zustand definieren lässt. Daraus könntest du prinzipiell unendlich viele Zustände bauen. NDTM's haben aber eine fixe anzahl an zuständen

ah , es gilt für die Zustandmenge Q folgendes

|q| < unendlich

=> endliche anzahl von zuständen, bin gespannt wie wir da die metazustände unterkriegen Augenzwinkern
 
 
Wolfskehl Auf diesen Beitrag antworten »

genau das habe ich ja auch gesagt. und das fehlte bei der begründung von wikipedia.

mir ist aber auch eigentlich kein problem bekannt wo z.b. 2^n im exponent steht. dir?

wirklich von interesse sind die ganzen NP-schweren bzw. NP-vollständigen probleme, z.b. TSP oder auch die frage wie man maschinen in einem gebäude kombinieren sollte, damit die transportwege minimal sind. es gibt da n! möglichkeiten. da ist das n im exponent, aber nicht a^n.
Mazze Auf diesen Beitrag antworten »

ich kenn ein problem das in 2^n liegt , das kann ich mit meinem Rechner lösen, ergo packt das auch ne turingmaschiene, wenn du es wissen willst ich kanns dir per PN schicken, da das problem in dem forum hier noch ne andere rolle spielt ^^

edit

du meisnt doch , da kenn ich keins -_-, vieleicht irgendeine extra abgefahrene grafenroutine oder so -_-
Wolfskehl Auf diesen Beitrag antworten »

stimmt. sie hat endlich viele zustände. das hindert sie aber nicht daran, mehrere befehle gleichzeitig auszuführen.

es könnte z.b. diese beiden 'befehle' geben:
1. wenn du dich in zustand X befindest und eine 1 liest, dann geh 1 schritt nach links, schreibe auf die 1 eine 0 und gehe in zustand Z.
2. wenn du dich in zustand X befindest und eine 1 liest, dann geh 1 schritt nach rechts, schreibe gar nichts und gehe in zustand V.

wenn sowas ein paar mal vorkommt, dann wächst die zahl der möglichen 'pfade' sehr schnell an. und sie würde auch hier 'raten' ob sie nun 1. oder 2. befolgen soll bzw. beide möglichkeiten 'gleichzeitig' abarbeiten.
Wolfskehl Auf diesen Beitrag antworten »

du meinst wo 2^n im exponent ist?

ok das kann schon sein. es spielt ja auch im praktischen eher eine rolle, wie groß das n ist, ob davor noch ein faktor steht und/oder eine konstante...

ok dann schicks mal.

krieg ich dann ne meldung wenn was kommt?
Mazze Auf diesen Beitrag antworten »

Zitat:
1. wenn du dich in zustand X befindest und eine 1 liest, dann geh 1 schritt nach links, schreibe auf die 1 eine 0 und gehe in zustand Z.
2. wenn du dich in zustand X befindest und eine 1 liest, dann geh 1 schritt nach rechts, schreibe gar nichts und gehe in zustand V.


vereinbare das bitte mit dem zustandsmodell, es ist nunmal so das auch eine NDTM durch ihre Zustände gekennzeichnet ist. Du kannst eins davon machen, nicht beides gleichzeitig, wohl aber hintereinander...

edit

ich hab mich revidiert ich dachte du meintes 2^n :P

wenn du mehrere Sachengleichzeitig machst, dadurch in unterschiedliche folgezustände gehst, dann müstest du die Kante quasi teilen. Sehr richtig, die kannte, es darf aber für eine Kante nur genau einen folge zustand geben. Es ist zwar erlaubt das eine Kante auf mehrere zustände zeigt, jedoch nicht das eine Kante in einem schritt auf mehrere geht.
Wolfskehl Auf diesen Beitrag antworten »

ja das meinte ich...

jedenfalls TSP hat nicht 2^n im exponent und ich kenne auch kein verwandtes wo es so ist.
Wolfskehl Auf diesen Beitrag antworten »

was ist denn da nicht gekennzeichnet?

ok ich weiß die syntax ist nicht korrekt. ist schon was her bei mir.

achso ok ich weiß.

naja man sollte nicht versuchen sich so eine TM real vorzustellen. das ist ja alles rein hypothetisch. es gibt dann halt zwei oder mehr pfade die jeweils eindeutig sind...das ganze ist ja nur ein modell.
Mazze Auf diesen Beitrag antworten »

hm, es gibt zweifellos Probleme die in

2^n liegen. Man kann doch einfach dieses problem künstlich erweitern in dem wir das Problem 2^n mal auswerten. Wir stellen uns einfach die frage wie lange dauert es das problem 2^n 2^n mal durchzurattern. Damit haben wir



was zwar totaler blödsinn is, aber ein "Problem" darstellt tt
Wolfskehl Auf diesen Beitrag antworten »

das dürfte die NDTM aber auch nicht in polynomineller zeit schaffen...oder?
Mazze Auf diesen Beitrag antworten »

dein Prof sagt doch aber nein verwirrt
Wolfskehl Auf diesen Beitrag antworten »

ja und ich meien das doch auch. aber bin mir nich 100% sicher...wobei...sollte man das wort des profs anzweifeln? ;-)
Mazze Auf diesen Beitrag antworten »

Zitat:
sollte man das wort des profs anzweifeln?


Naja, profs sind auch nicht unfehlbar, aber das se skill haben will ich nicht abstreiten :P Big Laugh
Wolfskehl Auf diesen Beitrag antworten »

hm naja ok..sie ist eigentlich nicht prof sondern doktor und ne frau...aber......sie hat den fehler in dem angebelichen beweis eines russen gefunden der behauptet hat das NP P problem gelöst zu haben

smile
Mazze Auf diesen Beitrag antworten »

Es gibt Beweise von Np = P oder NP !=P die waren hunderte von seitenlang, keine rhat was getaugt ^^
Wolfskehl Auf diesen Beitrag antworten »

die frage wäre halt wie man da vor geht, wenn man z.b. beweisen will, dass es ungleich ist. pumping lemma geht nicht, diagonalisierung auch nicht (laut meiner prof.). leider gibt es z.z. sehr wenige möglichkeiten, untere schranken für algorithmen zu bestimmen...

ich hatte dann noch die idee, dass man sich ja künstlich ein problem kreieren könnte, von dem man weiß, dass die zeit exponenziell sein muss und dann beweist, dass es NP-vollständig ist. aber woher nehmen? (also das problem)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »