Entscheidungsproblem mindestens so schwer wie Suchproblem?

...komplette Frage anzeigen

2 Antworten

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.

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.

Was möchtest Du wissen?