 |
 |
 |
 |
 |
 |
Startseite » Forum » Untere Schranke bei Linearen Reduktionen
Untere Schranke bei Linearen Reduktionen
Universität / Fachhochschule
Sonstiges
Tags: Komplexitätstheorie, Lineare, Reduktion, Sonstiges
 
|
  |
|---|
|
Hallo, ich habe eine Frage zu linearen Reduktionen aus der Komplexitätstheorie: Gegeben ist eine lineare Reduktion heißt "linear reduzierbar"), also man sagt: "A ist linear reduzierbar auf B". Nun ist zu zeigen, dass, wenn zur Lösung von A mindestens Omega(f(n)) Schritte notwendig, dann auch zur Lösung von mindestens Omega(f(n)) Schritte notwendig sind. Mit anderen Worten: jede untere Schranke für A ist auch eine untere Schranke für B. Meine Ideen bisher: heißt, dass A unter Zuhilfenahme von gelöst wird. - Der Algorithmus für wird dabei NUR EINMAL aufgerufen. - Das Programm für A benötigt OHNE den Aufruf von nur lineare Zeit (also . wird dann in Zeit gelöst, wobei die lineare Zeit OHNE Aufruf von ist und die Laufzeit des Algorithmus von meint. - Wenn die Lösung von A mindestens Omega(f(n)) Schritte erfordert, dann erfordert aber auch mindestens Omega(f(n)) Schritte. - Wie kann ich nun darauf schließen, dass auch (also die Zeit des Algorithmus zur Lösung von mindestens Omega(f(n)) Schritte benötigt? Ich würde mich über Hilfe sehr freuen! Vielen Dank schon im Voraus! |
|
|
|
|
Hallo, ich habe nun selbst eine Lösung gefunden, falls es wen interessiert: Der Beweis erfolgt durch Wiederspruch. Angenommen: braucht weniger als Omega(f(n)) Schritte, Element von mit . ist asymptotisch kleiner als . Das würde bedeuten, dass eine obere Schranke für ist und somit ist wegen der Voraussetzung auch eine obere Schranke für A. . laut Voraussetzung braucht A mindestens Omega(f(n)) Schritte, aber auch höchstens Schritte mit . Das kann aber nicht sein. Wiederspruch! Also folgt: braucht mindestens Omega(f(n)) Schritte zur Lösung. . |
1055789
1055325