Reduzierbarkeit < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:19 Mo 24.07.2006 | | Autor: | Bastiane |
Hallo zusammen!
Bei einem Beweis bin ich auf folgende "Frage" meinerseits gestoßen:
Wenn ich für Problem A die Laufzeit [mm] $\Omega(n\log [/mm] n)$ kenne und nun eine Schranke für Problem C haben möchte, reicht es dann, wenn ich A auf B reduziere und B auf C (ginge natürlich schneller, wenn ich A direkt auf C reduziere...), und dann weiß ich, dass C auch Laufzeit [mm] $\Omega(n\log [/mm] n)$ hat?
Umgekehrt hieße das dann doch, wenn ich für C die Schranke [mm] $O(n\log [/mm] n)$ kenne und genauso reduziere, wäre die Schranke für A auch [mm] $O(n\log [/mm] n)$ oder?
Wäre schön, wenn das jemand bestätigen könnte bzw. mir erklärt, was daran falsch ist.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:11 Di 25.07.2006 | | Autor: | Frank05 |
> Hallo zusammen!
Guten Abend,
> Wenn ich für Problem A die Laufzeit [mm]\Omega(n\log n)[/mm] kenne
> und nun eine Schranke für Problem C haben möchte, reicht es
> dann, wenn ich A auf B reduziere und B auf C (ginge
> natürlich schneller, wenn ich A direkt auf C reduziere...),
> und dann weiß ich, dass C auch Laufzeit [mm]\Omega(n\log n)[/mm]
> hat?
Die Reduktion ist transitiv, insofern spielt das nicht wirklich eine Rolle.
Aber du musst hier ein wenig aufpassen. Es gibt verschiedene Arten von Reduktionen, die durch entsprechende Einschränkungen der Reduktionsfunktion f unterschieden werden. In der Berechenbarkeitstheorie beispielsweise muss f total und berechenbar sein. Die "klassische" Reduktion ist die polynomielle Reduktion, wie sie für die NP-Vollständigkeitsbeweise meist benutzt wird, und dabei muss f total und in polynomieller Zeit berechenbar sein.
Um nun aber auf deine Frage zurückzukommen: Wenn ich das richtig sehe (ohne Gewähr), dann solltest du deine Reduktionsfunktion f so beschränken, dass [mm]f \in o(n\log n)[/mm]. Denn wenn C dann nicht in [mm]\Omega(n\log n)[/mm] entscheidbar ist (also schneller), dann kannst du A mit Hilfe des Algorithmus von C ebenfalls schneller entscheiden, was ein Widerspruch zur gegebenen Laufzeitabschätzung von A wäre.
> Umgekehrt hieße das dann doch, wenn ich für C die Schranke
> [mm]O(n\log n)[/mm] kenne und genauso reduziere, wäre die Schranke
> für A auch [mm]O(n\log n)[/mm] oder?
Hier musst du analog die Reduktionsfunktion einschränken. Du hast einen Algorithmus, der C in [mm]O(n\log n)[/mm] entscheidet und wenn du damit A in der gleichen Laufzeit entscheiden willst, dann muss deine Reduktionsfunktion [mm]f \in O(n \log n)[/mm] sein, da sonst der Entscheidungsalgorithmus für A von f dominiert wird.
> Wäre schön, wenn das jemand bestätigen könnte bzw. mir
> erklärt, was daran falsch ist.
Ich sehe jetzt nicht, was daran falsch ist (außer du lässt bel. polynomielle Reduktionsfunktionen zu), aber es ist schon spät und da kann man sicherlich auch etwas übersehen. Ich hoffe die Überlegungen helfen dir trotzdem ein wenig weiter 
|
|
|
|
