[carlosowas]

Man könnte die Vereinfachung ja zuerst mal an praktischen Fragestellungen ausprobieren. Deutsches Steuerwesen zum Beispiel. Da liesse sich aus dem np schon ein p machen, wenn man denn nur wollte. Und dann zerpflücke man den restlichen Gesetzesmüll bis man wieder auf p = die 10 Gebote ist.

Sehr gute Bemerkung. Die meisten Menschen, vor allem die aus den "trivialen" (trivial=dreiwegig) Fakultäten (Theologie, Jura, Philosophie, leben deshalb so gut, weil sie einfache Probleme unheimlich vernebeln und kompliziert machen. Die Theologie ist im Moment dabei, ihren guten Ruf zu verlieren, aber aus anderen Gründen.

[dreamtimer]

Ob theoretisch bewiesen oder unbewiesen, ein theoretischer Nachweis allein genügt nicht, um für ein praktisches NP-Problem auch tatsächlich einen P-Algorithmus zu finden. Denn der Beweis des Inders dürfte nicht konstruktiv sein.

Der Beweis versuchte ja genau das Gegenteil zu zeigen, dass eben P!=NP, also das, was auch jeder erwartet.

[Fackus]

... Sind Universen denkbar, in denen die Primzahlen nicht 1,3,5,7,11,13,... lauten, sondern anders verteilt sind? Damit wären wir naturgemäß nicht in der Lage, beliebig weit in die "Meta-Ebene" zu springen, ...

Das könnte schon damit anfangen, daß wir alles Denken auf ganzen Zahlen aufbauen und uns so zwangsläufig in irrationalen Zahlen (wie Pi) und damit in eine Metaebene des Unendlichen verrennen.
Nachdem sich unser Denken letztlich doch immer an dieser simplen ganzzahligen 1-2-3 Abzählerei orientieren muss, wird man über gewisse Erkenntnisgrenzen nicht hinauskommen - auch mit noch so vielen Primzahl- oder anderen Mathespielereien nicht.

[wulfaro]

Der Begriff Schwierigkeit ist zu allgemein gefasst, bei P und NP handelt es sich um Komplexitätsklassen, es geht hierbei um die Frage wie Aufwendig es ist die Lösung zu einem konkreten Problem zu finden.
Für alle Probleme in diesen Klassen gibt es Algorithmen mit dem sie sich lösen lassen, sie unterscheiden sich aber in Speicherplatzbedarf und der Laufzeit.
In NP ist der Aufwand extrem hoch, während in P er gut ist.

Bei der Frage P = NP ist von Interesse ob es Probleme gibt die sich nicht effizient lösen lassen.
Ob ein Problem lösbar oder unlösbar ist wird bei der Frage nach der Berechenbarkeit untersucht.

[Bias]

Und ein weiterer Artikel, der P und NP nicht korrekt definiert. Die Primzahlzerlegung ist deswegen so schwer, weil bisher niemand ein effizientes Verfahren gefunden hat. Das aber ist weder eine hinreichende noch notwendige Bedingung dafür, dass das Problem in NP ist. Btw, nicht die Primzahlzerlegung an sich ist nicht in NP, da NP eine Menge von formalen Sprachen ist. Das alles zu erklären ist mir jetzt aber zu anstrengend.

Irgendwas stimmt hier nicht.
Das sortierproblem habe ich verstanden:
k Zahlen, Anzahl Rechenschritte ist proportional zu kˆ2.

Wenn es aber stimmt, dass die Anzahl der Rechenschritte fuer die Primzahlzerlegung k^1/2 ist, so ist das Primzahlproblem bezueglich k natuerlich einfacher zu loesen.
Scheinbar wird gemeint, dass die Frage ist, wie schwierig es ist, eine k-stellige Zahl primzahlzuzerlegen. Dann gibt es die exponentielle Schwierigkeit.
Dann wuerde aber auch das Sortierproblem bei
(10^k)^2 liegen, also wuerde dies noch haerter sein als das Primzahlproblem...

Wir betrachten die Laufzeit stets im Verhältnis zur Eingabegröße. Hierbei zählt beim Primzahltest die Anzahl der Ziffern als Eingabegröße. Beim Sortieren ist das ebenfalls der Fall (wobei wir annehmen, dass die Eingabe durch die Ziffern 0 und 1 binär codiert ist), wobei man hierbei die Vereinfachung vornimmt, dass man nur die Anzahl der Zahlen betrachtet. Dies ist möglich, da dadurch die berechnete Laufzeit nur größer werden kann, wir also eine nichtschädliche Abschätzung nach oben durchführen. (Die Länge der Eingabe in Bits ist mindestens so groß wie die Anzahl der dadurch codierten Zahlen.)

[n01]

Allein schon die Berechnung , eine Torte in 2 Stücke zu teilen, ist sehr aufwendig. Mathematisch eigentlich sehr simpel. 1:2 = 0,5. Soweit die Theorie. Aber eine Torte praktisch genau zu teilen, ist fast unmöglich. Man müsste genau berechnen, aus wieviel Atomen die Torte besteht, dann die Torte möglichst genau in der Mitte teilen, und dann hoffen, das jede Hälfte die selbe Anzahl von Tortenatomen hat. Wenn nicht, wenn nur eine Hälfte ein Atom mehr hat, gibt es eine Unregelmäßigkeit. Rein rechnerisch ist es möglich , viele Dinge in der Natur zu berechnen. Aber da es immer unberechenbare Unwägbarkeiten gibt, wird man nicht umhin kommen, zu sagen, nicht alles ist berechenbar. Und deswegen, am Beispiel der Torte, schleichen sich in den Dingen Ungenauigkeiten ein. Nur ganz kleine, aber die unheimliche Menge der winzigen Ungenauigkeiten summiert sich zu etwas, worüber wir uns immer den Kopf zerbrechen Das Weltall ist ja auch nicht gerade, sondern irgendwie krumm. Wenn auch aus anderen Gründen. Es gibt wohl Dinge, die man mathematisch nicht erfassen kann im Leben, in der Technik und der Natur.

[der_rookie]

Es ist interessant, dass sie eine intrinsische Grenze aufzeigen. Halten Sie es für möglich, dass eine Grenze des Verstehens deshalb nicht bemerkt werden wird, da sie nicht nur in unserer Biologie, sondern fest im Universum kodiert ist? Sind Universen denkbar, in denen die Primzahlen nicht 1,3,5,7,11,13,... lauten, sondern anders verteilt sind? ...

Die Mathematik beruht nicht auf physikalischen Gesetzen und ist insofern nicht an unser Universum gekoppelt. Insofern ist sie auch keine Naturwissenschaft. Vielmehr mag als Teilgebiet der Logik bezeichnet werden: Wenn A, B und C gelten ("Axiome"), dann kann ich beweisen dass X, Y und Z gelten. Solange wir uns im Bereich der natürlichen Zahlen bewegen, werden also in allen denkbaren Universen dieselben Primzahlen existieren.
Vielleicht geht es aber umgekehrt: Vielleicht gibt es auch in unserem Universum andere Zahlensysteme mit anderen Primzahlen. Z.B. gibt es neben den natürlichen Zahlen auch andere Körper, Ringe und ähnliches für die man vielleicht auch Primzahlen definieren kann. Inwieweit diese sich dann allerdings in unserer physikalischen Welt als (anders) hilfreich als die üblichen Primzahlen nutzen lassen - keine Ahnung

[seine_unermesslichkeit]

Man könnte die Vereinfachung ja zuerst mal an praktischen Fragestellungen ausprobieren. Deutsches Steuerwesen zum Beispiel. Da liesse sich aus dem np schon ein p machen, wenn man denn nur wollte. Und dann zerpflücke man den restlichen Gesetzesmüll bis man wieder auf p = die 10 Gebote ist.

Und Hunderttausende Steuerschranzen sind auf einen Schlag arbeitslos. Das kann niemand wollen wollen!

[Bias]

Das Beispiel für ein NP-Problem ist denkbar ungünstig gewählt, da es nicht bekannt ist ob die Faktorisierung in NP liegt oder nicht. Da es einen Sub-Exponentialzeitalgorithmus gibt (Zahlenkörpersieb) ist die Laufzeit um RSA zu brechen sehr viel geringer als 2^O(n). Außerdem liegt das Problem in QP, der Klasse aller mit Quantencomputern effizient lösbaren Probleme, von der man wiederherum nicht weiß ob diese Klasse mit P übereinstimmt oder mit NP oder dazwischen liegt. Viele ähnliche Fragestellungen sind auch noch offen.

Jedes Problem aus P ist ebenfalls ein Problem aus NP. Ein Problem muss nicht exponentiellen Aufwand besitzen, um in NP zu liegen.

Oder habe ich Sie falsch verstanden?

[nordmatiker]

Irgendwas stimmt hier nicht.
Das sortierproblem habe ich verstanden:
k Zahlen, Anzahl Rechenschritte ist proportional zu kˆ2.

Wenn es aber stimmt, dass die Anzahl der Rechenschritte fuer die Primzahlzerlegung k^1/2 ist, so ist das Primzahlproblem bezueglich k natuerlich einfacher zu loesen.
Scheinbar wird gemeint, dass die Frage ist, wie schwierig es ist, eine k-stellige Zahl primzahlzuzerlegen. Dann gibt es die exponentielle Schwierigkeit.
Dann wuerde aber auch das Sortierproblem bei
(10^k)^2 liegen, also wuerde dies noch haerter sein als das Primzahlproblem...

Es geht um die "Input-Länge": Beim Sortierproblem sind k Zahlen gegeben. Bei einer k-stelligen Zahl sind es auch k Zahlen, nämlich die k Ziffern. Für das Sortierproblem braucht man in der Größenordnung k^2 Operationen. Zur Berechnung der Primfaktoren aber in der Größenordnung 10^(k/2). Das ist exponentiell in k, während das Sortierproblem nur quadratische Komplexität hat.