Diskussion:Suchproblem
Eigentlich sind Suchprobleme doch eine Verallgemeinerung von Entscheidungsproblemen. Anstatt polynomieller Reduktionen werden dort Turing-Reduktionen benutzt.
- Ähhm... ??? Entscheidungsprobleme haben erstmal nichts mit polynomieller Reduktion zu tun. Diese kommt erst bei der Frage ins Spiel, ob ein Problem NP-schwer ist. Ich gehe mal davon aus, das du mit Turing-Reduktion ganz allg. Reduktionen meinst und die spielen erst bei der Berechenbarkeit eine Rolle. Irgendwie ergibt die Frage für mich also gar keinen Sinn. Vielleicht kannst du sie noch mal präziser formulieren. Statt von einer Verallgemeinerung von Suchproblemen würde ich bei Entscheidungsproblemen von speziellen Suchproblemen sprechen. --Coma 06:10, 2. Feb 2005 (CET)
Ich würde Suchproblem anders definieren: Z. B. würde ich das Finden einer Lösung für ein SAT-Problem auch als Suchproblem bezeichnen, obwohl es dort nichts zu optimieren gibt. -- Roffle 08:30, 11. Apr 2005 (CEST)
- Hm, ja da könntest du recht haben, es gibt quasi "echte" Entscheidungsprobleme, wie SAT oder das Hamiltonkreisproblem, die nach der Existenz einer Lösung fragen und "künstliche" Entscheidungsprobleme, wie TSP, die nach der Existenz eine Lösung besser als ein x fragen, bei denen es in der Praxis aber immer um eine Optimierung geht. Insofern gibt es dann die zugehörigen Suchprobleme in beiden Fällen, aber nicht notwendigerweise das Optimierungsproblem. Fragt sich nur, wie man das jetzt möglichst geschickt und konsistent einbaut. --Coma 02:03, 12. Apr 2005 (CEST)
Ich wollte anregen für das bessere Verständnis der Unterteilung in Entscheidungs-, Optimierungs- und Suchproblem ein Beispiel einzufügen; z.B. für CLIQUE:
- Entscheidungsproblem: gibt es eine Clique der Größe K
- Optimierungsproblem: Anzahl der Knoten in einer maximalen Clique
- Suchproblem: finde maximale Clique
Frage: wohin sollte so ein Beispiel am besten kommen? Schließlich erstreckt sich die Problematik über drei Einträge...
- Am Besten in jeden der drei Artikel! --Coma 09:54, 16. Apr 2005 (CEST)
---
Ich will ebenfalls anmerken, dass unter "Suchproblem" in der Literatur meistens ein Problem verstanden wird, wo irgendeine Lösung ausgegeben werden soll oder "Nein" wenn es keine gibt -- im Unterschied zum Entscheidungsproblem, wo die Antwort bei positiven Instanzen nur "Ja" ist. Verwandt sind Aufzählprobleme, wo eben nicht nur irgendeine Lösung ausgegeben werden soll, sondern alle Lösungen. Vielleicht kann jemand den Artikel korrigieren... --84.114.18.215 23:56, 29. Jun. 2012 (CEST)
---
Der Artikel so wie er momentan ist, braucht dringend eine Quellenangabe. In vielen Büchern die das Thema behandeln, wird der Begriff Suchproblem nicht oder anders verwendet. (nicht signierter Beitrag von 2A02:908:672:D360:706C:C9B7:42B5:F9A1 (Diskussion | Beiträge) 09:03, 28. Okt. 2016 (CEST))