N np vollständig, lösung... sagt uns das was?

Wissenschaft Mathematik
#1

Hallo. Kurz mal in ein Gespräch mitbekommen wie einige öh glaube Mathestudis oder irgendwelche Ingenieure über was von n und np vollständig bzw. Beweisverfahren und Lösunsprobleme über np geredet haben (wobei ich nicht weiß welche Variablen die eigentlich mit n bzw. np gemeint haben). Naja ich weiß, das ist nicht viel und gerade doof in dem Raum geworfen :smile: Aber kann jemand damit was anfangen beziehungsweise „kurz“ erklären worums da geht oder was damit gemeint ist?

Wiegesagt, ich habe nicht gut zugehört nur zum Schluss „Also das muss jeder kennen, unglaublich dass sie das nicht gewusst hat“. Also denke ich ist das wichtig und hier kennt das jeder :smile:

Gruß

#2

Hallo,

vielleicht gibt Dir dies hier zumindest einen kleinen Anhaltspunkt.
http://de.wikipedia.org/wiki/NP-Vollst%C3%A4ndigkeit

Und noch ein kleiner Hinweis, das waren vermutlich Informatik-Studenten, wobei ich meine mich zu erinnern, dass wir auch in der Logik-Vorlesung mit diesem Thema Kontakt hatten. Ist auch nicht so wichtig, denn die Mathematik ist ja nunmal Bestandteil der Informatik. Für Informatiker ist es wichtig zu wissen, ob ein Problem in polynomieller Zeit lösbar ist. Ist es das nämlich nicht, dann ist die Laufzeit eines Programmes, das dieses Problem lösen könnte, auf jeden Fall erstmal jenseits von gut und böse. Und dann muss man versuchen, das Problem zu „reduzieren“.

Ich hoffe, ich habe Dir zumindest den Hauch einer Ahnung vermitteln können, worum es in dem Gespräch ging.

Gruss
Petra

#3

Hallo Petra,

ich habe mir gerade mal aus Neugier den Wiki-Artikel durchgelesen angesehen…
Kannst Du bitte mal ein kleines allgemeinverständliches Beispiel für so ein Problem geben? Also eins das sich nicht in polynomieller Zeit lösen läst.

Danke.
Olaf

#4

Eine Liste die aus einfachen Listen besteht, wobei jede Liste n Elemente hat benötigt für einen einfachen kompletten Durchlauf n^2 Zeiteinheiten. Diese Problem ist n-Vollständig lösbar.

Das Travalling-Salesman-Problem(Es gibt n Städte und ein Vertreter muss alle Städte abklappern in möglichst kurzer Zeit) lässt sich nicht durch ein Polynom wie n^2 oder n^3 beschreiben sondern eher mit was mit Fakultät.
Dieses Problem ist daher np-Vollständig

#5

Zum travelling salesman gehört für mich das dazu:

http://xkcd.com/399/

SCNR :o)

#6

Ah das sind schöne Beispiele. Gibt es eigentlich auch bzw. wann sagt man wenn etwas n / np nicht lösbar ist?

#7

Hallo,

ich versteh jetzt gerade nicht ganz, was Du meinst. Vermute aber mal, dass Deine Frage auf „Berechenbarkeit“ abzielt.

Hier noch 2 Links in diese Richtung:
http://de.wikipedia.org/wiki/Berechenbarkeit
http://de.wikipedia.org/wiki/Flei%C3%9Figer_Biber

Gruss
Petra