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

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Der letzte Beitrag

Shizmo

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