Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | Komplexitätsfunktionen als Äquivalenzrelation

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Komplexitätsfunktionen als Äquivalenzrelation

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Komplexitätsfunktionen als Äquivalenzrelation

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Komplexitätsfunktionen als Äquivalenzrelation

Zitatantwort auf diesen Beitrag erstellen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Shizmo: 31.05.2016 08:50.

21.05.2016 23:51

Nehmen Sie Shizmo in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Komplexitätsfunktionen als Äquivalenzrelation