k-fold exponential

Vorlesungen, Seminare und Praktika aus dem Bereich Theoretische Informatik (Abkürzungen)
Lectures, seminars and labs from the area Theoretical Foundations (Abbreviations)

k-fold exponential

Beitragvon errrso? » 07.09.10 19:13

"A function f is called at most k-fold exponential if f(m) is s_k(O(m)),where s_0(m)=m and s_{k+1}(m)=2^{s_k(m)} for every m \ge 1, k \ge 0."


Ah also ist s_3(O(m)) = 2^2^{O(m)} ? Was heißt das? Man kann doch keine Menge als Exponenten nehmen.
Benutzeravatar
errrso?
 
Beiträge: 55
Registriert: 20.11.08 21:08
Wohnort: Aachen

Re: k-fold exponential

Beitragvon fw » 07.09.10 19:50

Das ist eine schlampige Informatiker-Notation. Gemeint ist das selbe wie bei der "normalen" O-Notation auch. Es gibt eine Konstante c, so dass die linke Seite kleiner ist als 2^(2^(c*m)) (falls m groß genug ist).
Benutzeravatar
fw
 
Beiträge: 1356
Registriert: 17.05.06 19:37
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: Mathe

Re: k-fold exponential

Beitragvon MaoDelinSc » 09.09.10 04:42

errrso? hat geschrieben:Ah also ist s_3(O(m)) = 2^2^{O(m)} ? Was heißt das? Man kann doch keine Menge als Exponenten nehmen.


Wenn du eine Menge als Exponenten nimmst, ist damit die Menge aller Funktionen dieser Menge in die Basismenge gemeint, also bei 2^O(m) die Menge aller Funktionen von O(m) nach {1,2} (welche dann isomorph zur Potenzmenge von O(m) ist).

Das kann man hier also eigentlich nicht so schreiben, da O(m) ja die Menge aller Funktionen ist, die in dieser Komplexitätsklasse liegen und somit i.A. unendlich mächtig ist. Aber wenn fw sagt, die Informatiker machen das so, dann schreibt man es eben so xD

Gemeint ist also 2^2^2^2^2^...^2^O(m) = O(2^2^2^2^2^...^2^m) ;)
Was macht man, wenn man ein ungelöstes Problem hat?
Man gibt ihm einfach einen Namen!

(copyright Hawi)
MaoDelinSc
 
Beiträge: 296
Registriert: 07.12.07 10:28
Wohnort: Aachen
Studiengang: Informatik (B.Sc.)
Studiert seit: WS 09/10
Anwendungsfach: Medizin

Re: k-fold exponential

Beitragvon Alexander Urban » 20.10.10 16:03

MaoDelinSc hat geschrieben: 2^2^2^2^2^...^2^O(m) = O(2^2^2^2^2^...^2^m)
Und ich dachte immer, 2^O(m) sei ganz was anderes als O(2^m).
Nicht der Staat gewährt den Bürgern Freiheit, sondern die Bürger dem Staat Einschränkungen ihrer Rechte.

Kontrollierende und inhaltlich wertende Eingriffe in eine technologisch neutrale Infrastruktur sind eine Gefahr für den freiheitlichen Rechtsstaat.
Alexander Urban
 
Beiträge: 699
Registriert: 19.04.06 20:25
Wohnort: KaWo2
Studiengang: Informatik (Dipl.)
Studiert seit: SS 07
Anwendungsfach: Medizin

Re: k-fold exponential

Beitragvon Tommytb » 21.10.10 12:13

Alexander Urban hat geschrieben:
MaoDelinSc hat geschrieben: 2^2^2^2^2^...^2^O(m) = O(2^2^2^2^2^...^2^m)
Und ich dachte immer, 2^O(m) sei ganz was anderes als O(2^m).

definitiv :!:
"Man kann Nudeln machen warm, man kann Nudeln machen kalt."
Benutzeravatar
Tommytb
 
Beiträge: 427
Registriert: 27.05.06 16:56
Wohnort: Aachen
Studiengang: Informatik (Dipl.)
Anwendungsfach: E-Technik

Re: k-fold exponential

Beitragvon redmaniac » 22.10.10 10:55

Alexander Urban hat geschrieben:
MaoDelinSc hat geschrieben: 2^2^2^2^2^...^2^O(m) = O(2^2^2^2^2^...^2^m)
Und ich dachte immer, 2^O(m) sei ganz was anderes als O(2^m).


Ist es auch. So ist zB 2^{2n}\in 2^{O(n)}, aber 2^{2n}\notin O(2^n):

Zu bel. 0<c\in\mathbb{R},\; n_0\in\mathbb{N} wähle n>\max\{\log_2 c,\,n_0\}. Dann gilt wegen 2^{2n}=(2^n)^2, dass 2^{2n}=2^n \cdot 2^n>c\cdot 2^n.

Du sollte 2^{O(f)} lesen als die Menge aller Funktionen, die durch eine Funktion der Form 2^{g(x)} für g\in O(f) schließlich nach oben beschränkt werden.
'Offensichtlich' ist das gefährlichste Wort in der Mathematik.

Eric Temple Bell, Mathematiker, 1883-1960
redmaniac
 
Beiträge: 70
Registriert: 09.08.06 18:28
Wohnort: Aachen


Zurück zu Theoretische Informatik / Theoretical Foundations