Nicht NP-vollstaendige NP-Probleme |
| 16.03.2010, 19:34 | gitterrost4 | Auf diesen Beitrag antworten » | ||
| Nicht NP-vollstaendige NP-Probleme Ich weiss, dass dies eher Informatik ist, ich habe jedoch kein anstaendiges Informatikforum gefunden. Ich suche ein Beispiel fuer ein Problem , welches nicht NP-vollstaendig ist und welches (zumindest bekanntermassen) nicht in liegt. |
||||
| 16.03.2010, 19:35 | Iorek | Auf diesen Beitrag antworten » | ||
RE: Nicht NP-vollstaendige NP-Probleme
Siehe oben, da steht ein Link zum Informatikerboard 
|
||||
| 16.03.2010, 19:41 | gitterrost4 | Auf diesen Beitrag antworten » | ||
| RE: Nicht NP-vollstaendige NP-Probleme Danke dafuer. Just in dem Moment, in dem ich hier den Post abgeschickt habe, hat mir einer meiner Kommilitonen genatwortet und mich hierauf gestossen: http://en.wikipedia.org/wiki/NP-Intermediate Das beantwortet alles. Danke EDIT: Den Link zum Informatikerboard sehe ich leider immer noch nicht... aber das muss nichts heissen. |
||||
| 16.03.2010, 19:47 | Iorek | Auf diesen Beitrag antworten » | ||
Dann noch extra für dich, ein Bild im Anhang
|
||||
| 16.03.2010, 19:55 | papahuhn | Auf diesen Beitrag antworten » | ||
| RE: Nicht NP-vollstaendige NP-Probleme Ich habe noch nie von der NP-Intermediate Klasse gehört, aber habt ihr nicht in der Vorlesung behandelt, dass die Frage ob P = NP gilt, immer noch ungelöst ist? |
||||
| 16.03.2010, 20:12 | gitterrost4 | Auf diesen Beitrag antworten » | ||
| RE: Nicht NP-vollstaendige NP-Probleme Das ist klar. Die Frage war: Wenn gilt, ist dann Uebrigens: Bei mir gibt es die obige leiste nicht. |
||||
| Anzeige | ||||
|
|
||||
| 16.03.2010, 20:27 | Thomas | Auf diesen Beitrag antworten » | ||
@gitterrost: Hast du Javascript deaktiviert oder einen Adblocker eingeschaltet? Wenn du das für Matheboard erlaubst, sollte es gehen. |
||||
| 17.03.2010, 08:12 | gitterrost4 | Auf diesen Beitrag antworten » | ||
Ja, das kann gut sein. Haette aber nicht gedacht, dass grad die Leiste auf der ABP-Liste steht. Aber ich denke dies traegt nichts mehr zu diesem Thread bei. |
||||
| 17.03.2010, 11:25 | papahuhn | Auf diesen Beitrag antworten » | ||
| RE: Nicht NP-vollstaendige NP-Probleme Die Bedingung hast du aber vorher nicht hingeschrieben. Und selbst wenn: Wie soll man unter der Annahme, dass gilt, ein *konkretes* herbekommen? Da wird die Annahme doch zum Fakt. Naja, egal. |
||||
| 17.03.2010, 17:35 | gitterrost4 | Auf diesen Beitrag antworten » | ||
| RE: Nicht NP-vollstaendige NP-Probleme Ich habe es nur ungluecklich formuliert. Diese Annahme, dass P ungleich NP ist, sollte dieses "bekanntermassen" ausdruecken. Das sollte heissen, ein Problem, von dem man bisher nicht weiss, ob es in P liegt. Zu deiner Zweiten Anmerkung: Wie dem Wikieintrag zu entnehmen ist, hat Ladner ein konkretes Problem konstruiert, welches unter der Annahme, dass P ungleich NP ist, zwar in NP liegt aber weder in P noch in NPC. Beziehungsweise kann man doch ein Problem finden (jedes NP-vollstaendige Problem), fuer das gilt, P=NP oder das Problem ist in NP. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|