Diskussion:P-NP-Problem
aus Wikipedia, der freien Enzyklopädie
[Bearbeiten] Überarbeiten
Irgendwie stellt mich der Artikelname noch nicht zufrieden. Sollte es nicht P-NP-Problem heißen? Stern 23:33, 25. Mai 2004 (CEST)
- naja, eigentlich müsste es wohl P \stackrel{?}{=} NP (d.h. ein = mit einem Fragezeichen drüber) heißen, aber das ist doch wohl kein brauchbarer Artikelname... Aber nur diese Formulierung drückt das eigentliche Problem aus. --Pinguin.tk 23:58, 25. Mai 2004 (CEST)
Ich finde, der Artikel bedarf einer Überarbeitung, da es das größte ungelöste Problem der theoretischen Informatik ist. Das verdient einen starken, allgemeinverständlichen und ausführlichen Artikel, etwa wie in der englischen Wikipedia vorzufinden [1]. Ylloh 22:35, 18. Dez. 2006 (CET)
- Ich finde auch ,dass es mal ordentlich(!) überarbeitet werden muss.Und dabei sollte man am Namen des Artikels Anfangen . Ich bin für P versus NP
Nach P-NP-Problem verschoben und Einleitung überarbeitet--Spid 17:45, 15. Mär. 2007 (CET)
[Bearbeiten] Lösungsversuche
Vllt sollte man erwähnen ,dass es schon in der Vergangenheit versuche gab ,das Problem zu lösen : man siehe : Mikhail Kupchik: http://users.i.com.ua/~zkup/pvsnp_en.pdf oder Anatoly D. Plotnikov : http://www.heise.de/newsticker/meldung/12512
Es gibt jedoch viele Anzeichen dafür, dass tatsächlich gilt: P≠NP. Könnte man diese Anzeichen auch beim Namen nennen, nur um es nachprüfbar zu machen? --Bolliver 00:26, 5. Feb 2005 (CET)
Der Artikel ist sehr technisch. Ich finde man sollte versuchen auch Leute die nicht auf diesem Gebiet bewandert sind eine Chance zu geben die Problematik wenigstens annähernd zu verstehen. Eine sehr schöne und völlig von Fachbegriffen freie Erklärung dr Problematik habe ich auf der Seite des Clay-Preises gefunden: http://www.claymath.org/millennium/P_vs_NP/ Natürlich sollte der Rest auch bleiben...
Der Artikel ist eher theoretisch als technisch. Habe mir erlaubt ein wenig Alltagsnähe einzufügen. --84.174.222.145 18:42, 11. Okt 2005 (CEST)
"Ein alltägliches Problem ist das ausschneiden von Formen aus einem Kuchenteig" Müsste es nicht korrekterweise "beliebige Formen" heissen. Das Rucksack Problem geht doch davon aus, wenn ich mich nicht irre. Für bestimmte Formen gibt es doch zum Bsp. Lösungen aus der Algorithmischen Zahlentheorie. --80.129.139.50 02:07, 12. Okt 2005 (CEST)
Hmm.. Hat mein Info-Tutor gmeint. Aber sicher hast du recht, dass es um eine etwas andere Form des Rucksackproblems geht und "verschiedenen" sollte da schon stehen. Dann gibt es halt den Tradeoff zwischen "Wertigkeit" der Komponenten und Materialverbrauch. Es ist auch die Frage ob die mathmatische Lösung nicht eine elends hohe Laufzeit hat, kennt jemand eine solche? --84.174.140.160 08:12, 13. Okt 2005 (CEST)
Sagtmal, von euch hat nicht zufällig irgendjemand ne klitzekleine Idee für die Lösung? Unser Theo-Info-Prof meinte, jemand der ihm die Lösung zu diesem Problem präsentiert würde den Schein ohne Klausur bekommen. Und das erscheint mir derzeit als einfacher :D *scnr* --Patrick H 15:23, 31. Jan 2006 (CET)
Als nicht-Informatiker bzw nicht-Mathematiker hätte ich dazu eine kurze Frage, vorrausgesetzt jemand möge sie mir beantworten ;) Wie darf ich denn eine 'nicht-deterministische Turingmaschine' mir vorstellen, bzw den Unterschied einer 'deterministischen' und einer 'nicht-deterministischen'? Wäre nett wenn da jemand mir kurz weiterhelfen würde. Vielen Dank. :) --Cardiba 12:49, 18. Feb 2006 (CET)
@ Patrik: wenn ich die wüsste würde ich sie dir bestimmt nicht sagen sondern die 1 Mille € selber einkassieren @ Cardiba: Deterministisch = Vorherbestimmt Nichtdeterm. = Zufällig... @ beide: eigentlich gehört sowas nicht hierher, aber naja K. Ernst 20:08, 8. Apr 2006 (CEST)
Den Link auf den humoristischen Beweis würde ich persönlich entfernen. Er ist weder besonders lustig, noch relevant. Was meint ihr?
[Bearbeiten] PUBLIC-KEY
"Auf der (momentan) praktischen Unlösbarkeit von NP-Lösungsalgorithmen baut unter anderem das Public-Key-Verfahren auf."
Ist das so??? Ich glaube nicht.--88.64.146.65 03:12, 31. Jan. 2007 (CET)
- Warum denn nicht?
- http://de.wikipedia.org/wiki/RSA-Kryptosystem#Einwegfunktionen
- http://de.wikipedia.org/wiki/Einwegfunktion
- Mantra
Aus der Existenz von Einwegfunktionen folgt zwar P!=NP, aber die umgekehrte Richtung ist noch nicht bekannt. Ylloh 03:48, 24. Feb. 2007 (CET)
Aus Faktorisierungsverfahren: Beim Faktorisierungsproblem für ganze Zahlen ist nicht bekannt welcher Komplexitätsklasse es angehört.--Spid 16:01, 8. Mär. 2007 (CET)
