Diskussion:NP-Schwere

Automatische Archivierung

Auf dieser Seite werden Abschnitte ab Überschriftenebene 2 automatisch archiviert, die seit 90 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind.

Archiv

ab 2004

Wie wird ein Archiv angelegt?

Artikel löschen wegen Thema verfehlt

Seit wenigstens sechs Jahren scheint dieser Artikel nun zu existieren und ist immer noch unverständliches, arrrogantes Fachgeschwurbel. Wenn es nicht gelingt eine Sprache (vorzugsweise Deutsch und nicht Informatikerkauderwelsch) und eine Wortwahl innerhalb dieser Sprache zu finden, die auch über den Vorsitzenden einer Informatikerprüfungskommission hinaus verstanden wird, ist der Artikel hier einfach deplaziert. Er wirft mehr Fragen auf als daß er Antworten gibt. Den Text kann ich so oder ähnlich wahrscheinlich in mehreren Fach/Lehrbüchern oder Vorlesungsunterlagen finden, verstehen tue ich ihn aber nur, wenn ich die 200 Seiten davor auch verstanden habe. Es ist gut, daß diese 200 Seiten dem Artikel nicht vorangestellt wurden.

In der vorliegenden Form ist dies ein weiterer Artikel nur für Leute, die überprüfen können und wollen, ob der Autor den Lehrstoff widergeben kann. Deshalb ist der Artikel wegen Thema verfehlt zu löschen. Thema ist nämlich: Erkläre NP-Schwere jemandem, der es nicht schon vorher besser weiß! Ebenso auf Löschung zu prüfen sind die Artikel, die diesen Artikel zur Erklärung/Verwirrung verwandter Begriffe verlinken. Wenigstens sind zur Konfusionsverringerung die Links zu löschen.

Wer einmal die Originaltexte von Einsteins Relativitätstheorie(n) gelesen hat, wird überrascht sein, wie einfach und anschaulich man ein so anspruchsvolles Thema im vollständigen deutschen Satz vermitteln kann. Das Ganze ist nicht schwieriger zu lesen und zu verstehen als ein achtseitiger Spiegelartikel über regenerative Energiewirtschaft. Und wer einen deutschen Schulabschluß und einen deutschen Führerschein hat sollte mit einem Spiegelartikel nicht überfordert sein.

CBa--80.137.52.176 16:19, 2. Aug. 2010 (CEST)

Die Komplexitätstheorie ist eines der schwierigsten Themen der Theoretischen Informatik und wird hier durchaus anschaulich erklärt. "Theoretische Informatik for Dummies" gibt es nicht. Sorry. Die geäusserte Kritik ist an Arroganz nicht zu überbieten.

--mikl (Diskussion) 13:56, 2. Mai 2013 (CEST)

Ich finde auch, dass die Einleitung dieses Artikels einfacher geht - die Kritik ist auf jeden Fall berechtigt. Den Rest finde ich aber gut. Ok, ich habe noch einmal die Einleitung gelesen, vielleicht kann eine wordgewandte Person Nichtdeterministische Polynomialzeit besser erklären. Das wäre eine erhebliche Verbesserung.141.76.110.235 11:52, 6. Mai 2013 (CEST)

Und als nächstes fordern wir, dass sämtliche Artikel über Mathematik rest- und ersatzlos aus der Wikipedia gestrichen werden. Immerhin verstehen nicht alle Leute etwas von Mathematik! Und wenn wir dabei sind, machen wir gleich mit allen Artikeln über das Finanz- und Handelssystem weiter - ist ja schließlich nicht jeder Mensch Börsenmakler, der etwas davon versteht. Aber hauptsache man rastet erstmal auf der Diskussionsseite aus, nur weil man ein paar sehr simple Grundlagen nicht kennt. Artikel wie z.B. Euler-Lagrange-Gleichung sind da deutlich schwieriger zu verstehen und benötigen deutlich mehr Vorwissen. Dieser Artikel hier ist aber extrem einfach zu verstehen und benötigt so gut wie kein Vorwissen (was ein Polynom ist oder was eine formale Sprache ist, sollte ja wohl jeder wissen, der solch einen Artikel liest, was er ja schließlich auch nur dann tut, wenn er sich mit dem Thema beschäftigt).

--IUniversEi (Diskussion) 13:37, 31. Mai 2013 (CEST)

Ich möchte mich der obigen Kritik anschließen, wenn auch etwas sanfter. Der Artikel ist für Informatiker tatsächlich sehr anschaulich geschrieben. Allerdings fehlt der entscheidende Satz in der Einleitung, der "NP-schwer" als etwas greifbares definiert.

Dazu nun folgender Vorschlag: NP-schwer heißt ein Problem dann, wenn es entweder von einer nichtdeterministischen Turinmaschine in Polynomialzeit gelöst werden kann (bspw. Quantencomputer, also eher theoretische Möglichkeit) oder von einer deterministischen Turinmaschine in expotentieller Zeit (klassischer Computer). Dies bedeutet praktisch, dass der zeitliche Rechenaufwand für np-schwere Probleme mit deren Umfang exponentiell zunimmt. So sind die meisten np-schweren nicht adäquater Zeit lösbar. Vielleicht kann man auch noch die Ameisenalgorithmen darauf verlinken, um es zu veranschaulichen. Mir selbst ist der Begriff sehr oft im Themenfeld des Maschinellen Lernens untergekommen, wobei er immer in Beziehung dazu genannt wurde, dass ein Problem nicht zeiteffizient lösbar ist. Ich habe mich nie für NP-Schwere interessiert, sondern wollte lediglich wissen, was dieser Begriff bedeutet, sodass ich in meinem Bereich weiterlesen kann.

Stimmt das so? Vielleicht kann man es ja gleich per copy&paste in den Artikel einfügen oder ich mache es selbst.

--Moedn (Diskussion) 14:55, 25. Nov. 2015 (CET)

Nein, das kann man so nicht übernehmen. Schon alleine der Schluss ("Dies bedeutet praktisch, dass der zeitliche Rechenaufwand für np-schwere Probleme mit deren Umfang exponentiell zunimmt.") ist einfach falsch. Das mag für Dich eine gute Annäherung ans das Thema darstellen, ist aber nicht korrekt, da es eine schwammige Formulierung einer unbewiesenen Vermutung ist. Ich finde die Einleitung, die ja ein wenig braucht, um zum Lemma zu kommen, auch nicht prickelnd, aber eine mehr gefühlte denn exakte Definition bringt uns in der Einleitung eines Enzyklopädieartikels leider auch nicht weiter. --mirer (Diskussion) 17:36, 25. Nov. 2015 (CET)

Ein Quantencomputer kann keine NP-schweren Probleme lösen. Er kann beispielsweise schnell faktorisieren oder schnell diskrete Logarithmen berechnen. Es sind zwar keine Algorithmen bekannt, die diese Probleme auf einem klassischen Computer in Polynomialzeit lösen (was nicht heißt, dass es keine gibt!), aber es handelt sich auch nicht um NP-schwere Probleme. 79.245.169.201 22:55, 19. Feb. 2016 (CET)

uebersetzung

bei uebersetzungen muss nach WP:Übersetzungen vorgegangen werden, sonst liegt eine urheberrechtsverletzung vor. ich habe daher die letzten aenderungen rueckgaengig gemacht. --Mario d 12:34, 12. Mär. 2012 (CET)

Das ist kein Grund das zurückzusetzen. Man hätte hier auf der Diskussionsseite den Übersetzungsbaustein setzen können!! Siehe WP:Übersetzungen. Bitte in nächster Zeit die zurückgesetzten Änderungen wieder einbauen. Die enthielten viel Information!--92.203.77.212 19:40, 13. Jun. 2012 (CEST)

ja das haette man. allerdings finde ich den englischen artikel nicht besonders gut und die uebersetzung wies einige typische uebersetzungsprobleme auf und haette noch einiger ueberarbeitung bedurft. ich wuerde vorschlagen, das wenige, was dem artikel noch fehlt, einfach neu zu schreiben. damit sparen wir uns die uebersetzungsprobleme. --Mario d 13:33, 14. Jun. 2012 (CEST)

Intuition

"Beispielsweise ist das Quadrieren einer Zahl reduzierbar auf die Multiplikation zweier Zahlen, denn jeder Algorithmus, der zwei Zahlen multiplizieren kann, kann auch eine Zahl quadrieren (indem er sie mit sich selbst multipliziert). Multiplizieren ist also in diesem Sinne mindestens so schwer wie Quadrieren."

Heisst es nicht eigentlich, das reduzieren von der Multiplikation auf das Quadrieren? 77.21.75.220 17:38, 16. Feb. 2013 (CET)

nein, wie kommst du darauf? --Mario d 18:17, 16. Feb. 2013 (CET)

nein, reduzieren bedeutet soviel wie "zurückführen auf ein einfachereres Problem". Da quadrieren "komplizierter" ist und es auch in mehrere Multiplikationsschritten beschrieben werden kann. Genauso ist auch das Multiplizieren auf Addieren zurückzuführen. Stell dir vor, du müsstest 8 Mal 256 rechnen, dein PC kann aber nur addieren. Dann gibst du einfach 256+256+...[8 Mal] ein. 141.76.110.235 11:41, 6. Mai 2013 (CEST)

NEIN ! - In der Komplexitätstheorie bedeutet "Reduzieren" eben gerade im Gegenteil "Zurückführen auf ein mindestens genauso schwieriges Problem" - und genau darum entsteht öfter diese Verwirrung. Die Formulierung im Artikel ist korrekt: Multiplizieren ist auf jeden Fall nicht einfacher als Quadrieren, ansonsten würde ein Algorithmus für das einfachere Problem ja nicht ausreichen, um das schwierigere zu lösen. Anschaulich drückt sich das auch in der Notation $A\preceq _{\rm {p}}B$ aus, die bedeutet, dass es eine Polynomialzeitreduktion von Problem A auf B gibt, B also nicht kleiner (bzgl. Rechenzeitbedarf) ist.--Graf Alge (Diskussion) 17:00, 22. Okt. 2013 (CEST)

Schwere oder Schwierigkeit?

Hallo! Ich bin immer wieder etwas überrascht die Übersetzung von "hard" als "schwer" zu lesen. Ich sehe ein, dass es als Adjektiv noch halbwegs Sinn ergibt, da "schwer" und "schwierig" durchaus synonym verwendbar sind. Aber ist Schwere wirklich so klar im Sinne von Schwierigkeit? Ich assoziiere das immer mit Gewicht und Masse. In den Fachbüchern von Ingo Wegener [1, 2] bspw. ist durchgängig von "schwierig" die rede.

[1] Wegener, I. Komplexitätstheorie. Springer-Verlag Berlin Heidelberg, 2003.

[2] Wegener, I. Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner Verlag, 2005. (nicht signierter Beitrag von 93.233.2.58 (Diskussion) 13:59, 28. Okt. 2016 (CEST))

finde schiwerig auch deutlich besser...schwere ist ziemlich daneben. Shaddim (Diskussion) 21:23, 9. Jul. 2017 (CEST)

Außer Halteproblem

Gibt es andere Probleme, von denen bewiesen wurde, dass sie NP-schwer sind aber nicht in NP liegen außer dem Halteproblem (das nimmt ja immer eine Sonderstellung ein) ?--Claude J (Diskussion) 09:44, 27. Aug. 2017 (CEST)

Da wären einmal die unentscheidbaren Probleme: Das Halteproblem hast du ja schon erwähnt es gibt aber noch unzählige (überabzählbar viele) andere. Ein nettes Beispiel ist das Postsche Korrespondenzproblem.

Andererseits gibt es auch entscheibare/berechenbare Probleme deren Komplexität höher als NP ist (also NP-schwer aber nicht in NP). Hier kann man einfach mal bei den höheren Komplexitätsklassen nachschauen, z.B., NEXPTIME und EXPSPACE.

Es ist bekannt das NP eine echte Teilmenge von NEXPTIME ist. Daher jedes Problem das NEXPTIME-schwer ist ist auch NP-schwer aber eben nicht in NP. Das gleiche gilt für alle Komplexitätsklassen die NEXPTIME umfassen, wie eben EXPSPACE.

Hoffe das hilft dir weiter -- Wdvorak (Diskussion) 14:09, 28. Aug. 2017 (CEST)