Diskussion:NP-Schwere/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:NP-Schwere/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung auVorlage:SSerhalb der Wikipedia

https://de.wikiup.org/wiki/Diskussion:NP-Schwere/Archiv/1#Thema_1

Deutung

NP-Schwere scheint mir aus dem zur Zeit bestehendem Artikel nicht verständlich. Ein einleitender, erläuternder Satz ist nicht vorhanden. Die Bestandteile der Formel sind nicht erläutert. --Dirk33 22:26, 5. Apr 2004 (CEST)

Sehe ich genauso. Der Artikel sagt wahrscheinlich allein dem/der AutorIn etwas... MichaelB. 02:12, 6. Apr 2004 (CEST)

Alle Bestandteile der Formel sind erläutert und ausformuliert vorhanden. Was genau fehlt Euch? Stern 02:15, 6. Apr 2004 (CEST)

Hallo Stern leider sehe keinen einleitender, erläuternder Satz, "Sei $L_{1}\subset \Sigma ^{*}$, also eine formale Sprache" ist für mich nicht direkt zu verstehen.

Bezüglich Erläuterungen der Formel meine ich

Was ist:

$L_{1}$

$\Sigma ^{*}$

$\forall L$

$NP$

$L$

$\leq _{P}$ --Dirk33 22:24, 6. Apr 2004 (CEST)

Konnte auch nicht nachvollziehen was $L_{1}$ sein sollte. Vermutlich ein Tippfehler der $L'$ meint. Habe es ersetzt. SatanClaus 01:30, 4. Jul. 2008 (CEST)

Das ist nur für Mathe-Akademiker verständlich. Ich bin gewiss nicht schlecht in Mathe aber dies ist - wie die gesammte Komplexitätslehre - math. Theorie und sollte daher sehr ausführlich, also mit Worten, beschrieben werden. Benutzer Augiasstallputzer; 14:52, 13. Feb. 2007 (CET)

Ich denke Korrektheit ist wichtiger als Verstaendlichkeit. Und wenn diverse Thematiken nunmal fuer Ottonormalmensch irrelevant sind, kann man nicht erwarten dass man diese mit purer Absicht auf ein Niveau runterkuerzt dass sie schon wieder falsch dargelegt werden. Es ist eben wie es ist. Ein "Mathe-Akademiker" wird es im Uebrigen kaum verstehen, da es sich um einen Begriff aus der theoretischen Informatik handelt. :-)

Als "Nicht-Informatiker" kann ich diesen Artikel leider nicht nachvollziehen. Schade. Ich denke auch, dass Korrektheit am wichstigsten ist, allerdings könnte man doch die Verständlichkeit als "Und hier eine verständliche (aber leider nicht ganz zutreffende) Erklärung" am Ende anfügen oder zumindest hier auf der Diskussionsseite in Prosa erläutern. Danke Walli

Ich hab mal die Einleitung ein wenig umgeschrieben, bin selbst auch eher vom Fach, aber als "nocht nicht ganz Fertiger" wohl noch ein wenig in der Lage das mit einfachen Worten zu umschreiben. Ginge das so in Ordnung? Wuerde ausserdem das Beispiel etwas simpler waehlen und.. Ja.. frage mich sowieso warum die NP-Schwere nicht unter polynomieller Reduktion abgehandelt wird, wird soweit ich weiss auch nur dort verwendet oder? --Schwarzer8Kater 18:32, 18. Feb. 2008 (CET)

Zu kurz, schlechte Darstellung

Selbst mir als Informatiker ist diese Beschreibung von NP-Schwer zu kurz und es fehlen ein paar wichtige dazugehörige Schaubilder. Wie ist der Zusammenhang zwischen der Klasse der NP-Schweren Probleme und anderen Komplexitätsklassen (als Diagramm, nicht nur mit der Klasse der NP-vollständigen Probleme)? Das angegebene Beispiel ist zwar richtig, doch viel zu unkonkret für ein Beispiel, als dass man daraus etwas sehen könnte. Was sind die Konsequenzen falls P=NP und was falls P!=NP? (nicht signierter Beitrag von 129.13.186.1 (Diskussion | Beiträge) 4:26, 18. Apr. 2008 (CEST))

Das steht unter P-NP-Problem. -- ri st 19:41, 23. Jul. 2009 (CEST)

Begriff NP-Schwer

Wenn wir schon versuchen, NP-hard korrekt zu übersetzen, dann sollten wir vielleicht NP-schwierig schreiben, denn dann ist gleich eindeutig, worum es hier geht: Um die Klassifizierung von Problemen anhand der Schwierigkeit sie algorithmisch zu lösen. (nicht signierter Beitrag von 85.179.51.38 (Diskussion | Beiträge) 15:29, 10. Jan. 2009 (CET))

Das sehe ich auch so. -- ri st 17:26, 23. Jul. 2009 (CEST)

Offenbar hat sich dort noch immer nichts getan. Ich denke, dass man "NP-schwere" durchaus stehen lassen kann, da es sich hier um ein Hauptwort handelt. Man könnte allerdings an geeigneter Stelle in der Einleitung bemerken, dass man üblicherweise nur das Adjektiv "NP-schwierig" verwendet. Diese Lösung erscheint mir am sinnvollsten. (So sagt man im Englischen ja auch nicht NP-hardness.)--BercherP 11:12, 30. Okt. 2009 (CET)

Begriff NP-hart

Ich halte den ersten Satz "NP-Schwere bzw. NP-Härte (Fehlübersetzung des englischen NP-hard, abgekürzt für Non-deterministic Polynomial-time hard) ist ein Begriff aus..." für zu gutmütig. Zwar geht aus ihm (korrekt) hervor, dass das Wort "NP-hart" falsch ist, aber rein optisch wird dies nicht deutlich genug hervorgehoben. Was ich damit meine: Zwar geht aus dem Inhalt des Satzes hervor, dass "NP-hart" falsch ist, die syntaktische Darstellung des Satzes suggeriert aber, dass NP-Härte synonym zu lesen ist wie NP-Schwere. Dies wird suggeriert, da NP-Härte fett gedruckt ist, durch ein "bzw." angebunden wird und sich "auf derselben Ebene" befindet wie NP-Schwere. Ich würde den Satz wie folgt umformulieren: "NP-Schwere (aufgrund einer Fehlübersetzung des englischen NP-hard, abgekürzt für Non-deterministic Polynomial-time hard, oft auch als NP-Härte bezeichnet) ist ein Begriff aus..." Sofern ich noch eine Zustimmung erhalte, übernehme ich diesen Vorschlag. --BercherP 11:12, 30. Okt. 2009 (CET)

Also meine Zustimmung hättest du, ich empfinde die Änderung als Verbesserung (da ich vorhin dreimal den Einleitungssatz gelesen habe, bis ich wusste, wie's gemeint ist..) --Kraymer 17:10, 23. Dez. 2009 (CET)

Bsp. / Halteproblem

"Darüber hinaus liegt das Halteproblem aber selbst nicht in NP, da es überhaupt nicht entscheidbar ist."

Diese Aussage erscheint mir unsinnig. Das Halteproblem ist nicht entscheidbar. NP fordert keine Entscheidbarkeit. NP bedeutet bezogen auf das Halteproblem: Für Eingaben, für die die TM hält, kann dies nichtdeterministisch in polynomieller Zeit festgestellt werden. (Für Eingaben, auf denen die TM nicht hält, ist nicnts ausgesagt.) (nicht signierter Beitrag von Bri B. (Diskussion | Beiträge) 10:52, 15. Feb. 2010 (CET))

doch, die gesamte komplexitätstheorie setzt die entscheidbarkeit voraus. man kann es sich auch so vorstellen, dass unentscheidbares unendliche laufzeit benötigt. (nicht signierter Beitrag von 84.157.227.179 (Diskussion) 19:44, 8. Aug. 2011 (CEST))