Komplexitätstheorie

[Jester]

Jetzt mach doch erstmal den ersten beweis fertig. Und vergiss das W. Das ist doch nur ein "kann funktion nicht umkehren, also geb ich der umkehrfunktion halt nen namen und rechne damit weiter"

[Sone]

Jester schrieb:

Jetzt mach doch erstmal den ersten beweis fertig. Und vergiss das W. Das ist doch nur ein "kann funktion nicht umkehren, also geb ich der umkehrfunktion halt nen namen und rechne damit weiter"

Ja, aber ich komme hier nicht weiter:

$n^{100} < \epsilon 2^{\frac{n}{100}}$
Davon habe ich leider nichts. Ich kann das Umformen wie ich will, aber ...

Ein Ansatz wäre folgendes:

$\frac{n^{100}}{2^{\frac{n}{100}}} < \epsilon$
Nun ist zu beweisen, dass der Bruch für n → ∞ gegen Null läuft - und damit zwangsläufig auch unter →.
Also in anderen Worten, dass der Nenner größer und größer als der Zähler wird.

Im OP habe ich schon eine Überlegung geäußert - man verdoppelt das Funktionsargument, und zeigt, dass ab n > 10000 der Faktor beim Nenner größer wird. Und dieser dadurch immer schneller steigt als der Zähler.
Da wenn eine Funktion f schneller steigt als eine Funktion g, f diese zwangsläufig überholen und die Differenz gegen ∞ geht... reicht das aber alles für einen Beweis?
Ich kann dann zeigen, dass für jedes ε ab einem bestimmten n das Verhältnis von g zu f groß genug ist, sodass die Ungleichung erfüllt ist.

[dot]

Ohne den Thread ganz genau gelesen zu haben: Du kannst beide Seiten einer Ungleichung durch eine stetig streng monoton steigende Funktion schicken und die Ungleichung hält immer noch. Alle Werte sind strikt positiv; ich schlage den Logarithmus zur Basis 2 vor...

Alternativ könntest du auch mit der Definition über den Limes arbeiten. Dort könnte das hilfreich sein: http://de.wikipedia.org/wiki/Regel_von_L’Hospital

[Sone]

Ja, das war ein guter Tipp!
100 mal ableiten ergibt:

$\frac{100!}{ (\frac{ln 2}{100})^{100} 2^{\frac{n}{100}} }$

Und da dieser Bruch konvergiert (für x → ∞ läuft er gegen 0), ist die Regel anwendbar!

Das heißt, damit habe ich eigentlich bewiesen, dass der Bruch gegen Null läuft. Un dass damit für jedes ε ein n existiert, welches dieser Ungleichung genügt...
(Bzw. jetzt kann man es sehr leicht aufzeigen)

[dot]

Oder eben z.B.

\begin{align*} n^{100} &< \epsilon \cdot 2^{\frac{n}{100}} \\ \Leftrightarrow\; \log\_2\left(n^{100}\right) &< \log\_2\left(\epsilon \cdot 2^{\frac{n}{100}}\right) \\ \Leftrightarrow\; 100 \cdot \log\_2(n) &< \log\_2(\epsilon) + \frac{n}{100} \\ \end{align*}

[Sone]

Das hatte ich schon längst.

[dot]

aber?

[Sone]

dot schrieb:

aber?

Wie hätte ich das gebrauchen können? n ist immer noch auf beiden Seiten der Ungleichung.
Durch den genialen Tipp mit L'Hospital habe ich n in einen Term gebracht.

[dot]

Aber der log(n) wird ab einem bestimmten n immer kleiner sein als n...

[Sone]

dot schrieb:

Aber der log(n) wird ab einem bestimmten n immer kleiner sein als n...

Oh! Stimmt. Ich bin halt dumm.

[Sone]

dot schrieb:

Aber der log(n) wird ab einem bestimmten n immer kleiner sein als n...

Ja, aber wie berechne ich n?

[Sone]

Hier ist die Ungleichung gelöst:

$n > log_2( \frac{100!}{(\frac{ln 2}{100})^{100}} ) * 100$

Einfach wunderschön.

[dot]

Wie kann das sein, dass deine Lösung unabhängig von $\epsilon$ ist?

[Sone]

dot schrieb:

Wie kann das sein, dass deine Lösung unabhängig von $\epsilon$ ist?

Verallgemeinere ich gerade.

[Sone]

Ja, die Lösung ist, einfach das Epsilon einfügen:

$n > log_2( \frac{100!}{\epsilon (\frac{ln 2}{100})^{100}} ) * 100$

Gut, das heißt, das hätte ich dann geschafft.