Informatiker Board | Druckvorschau: Komplexitätsfunktionen als Äquivalenzrelation

Geschrieben von Shizmo am 21.05.2016 um 23:51:

Komplexitätsfunktionen als Äquivalenzrelation

Hallo,

Zitat:

Sei $[latex]M:= \{f|f:\mathbb{N}\rightarrow \mathbb{R}^+ \}[/latex]$ die Menge aller Komplexitätsfunktionen von $[latex]\mathbb{N}[/latex]$ nach $[latex]\mathbb{R}^+[/latex]$ . Wir definieren die Relation $[latex]\sim[/latex]$ wie folgt: Für zwei Funktionen $[latex]f,g \in M[/latex]$ gilt $[latex]f\sim g \iff f \in \Theta(g)[/latex]$ . Zeigen Sie, dass $[latex]\sim[/latex]$ eine Äquivalenzrelation ist.

Leider weiß ich nicht, wie ich die Symmetrie am besten formal "beweise".

LG