Frage von klauszi, 44

Entscheidungsproblem mindestens so schwer wie Suchproblem?

In unserer Vorlesung wurde uns berichtet, dass in vielen Fällen das Suchproblem auf das Entscheidungsproblem polynomial reduzierbar wäre, sodass man annehmen kann, dass das Suchproblem entweder gleich oder leichter als das Entscheidungsproblem ist?!

Wenn ich nun ein Problem habe ( beispielsweise minimalste Knotenüberdeckung), dann ist die Entscheidung, ob eine Instanz falsch oder richtig ist, doch deutlich schneller herauszufinden, als wenn man die tatsächliche Lösung findet?!!!!

Hilfe!

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von ralphdieter, 11

Ein Entscheidungsproblem kann immer mit dem entsprechenden Suchproblem gelöst werden. Ist keine konkrete Lösung gefragt, kann's höchstens schneller gehen.

Ein Suchproblem über eine baumartige Menge kann Teilbäume mithilfe eines passenden Entscheidungsproblems abschneiden. Im Idealfall reduziert es sich so auf "polynomial viele" reduzierte Entscheidungsprobleme. Falls das gelingt, ist das Suchproblem nur "polynomial komplexer" als das Entscheidungsproblem. Von "leichter" ist hier nicht die Rede.

Die Verifikation einer gegebenen Lösung ist in der Regel trivial.

Am Beispiel der minimalen Knotenüberdeckung:

  • Das Entscheidungsproblem stellt fest, ob eine Überdeckung mit höchstens k Knoten existiert. Notfalls kann es nach einer solchen suchen, aber vielleicht geht's auch schneller.
  • Das Suchproblem berechnet eine Überdeckung mit höchstens k Knoten. Nützlich ist dabei eine schnelle Entscheidung, ob ein Teilgraph eine Überdeckung mit höchstens k' Knoten besitzt. Könnte man das in Polynomialzeit herausfinden, wäre wohl auch das Suchproblem effizient lösbar.
  • Die Verifikation, ob eine Überdeckung höchstens k Knoten enthält, ist dabei banal.
Antwort
von Schachpapa, 11

Beim Entscheidungsproblem muss ein Programm entscheiden, ob eine Aussage wahr oder falsch ist (indem es eine Beweiskette findet) Bei deinem Beispiel geht es darum, eine Lösung zu einem Problem zu finden, die - wenn man sie hat - leicht (in Polynomialzeit) zu verifizieren ist. Mir fällt da immer die Primfaktorenzerlegung ein: Wenn du eine große (1000 Stellen) Zahl hast, die das Produkt aus zwei unbekannten Primzahlen ist, ist es praktisch unmöglich, diese Faktoren zu ermitteln. Wenn du sie aber hast, kannst du die Richtigkeit deiner Lösung durch einfache Multiplikation belegen. Trifft zwar nicht genau deine Frage, hilft aber hoffentlich weiter.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten