Theoretische Informatik

ETH Theoretische Informatik

Frage zuerst
Antwort zuerst
Selbsttest

5.0 (1)

Lernen

Kartei Details

Karten	15
Sprache	Deutsch
Kategorie	Informatik
Stufe	Universität
Erstellt / Aktualisiert	28.12.2020 / 15.02.2021
Lizenzierung	Keine Angabe
Weblink	https://card2brain.ch/box/20201228_theoretische_informatik
Einbinden	<iframe src="https://card2brain.ch/box/20201228_theoretische_informatik/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>

Flip-Modus

Definiere \(\text{Space}_M(n)\)

\(\text{Space}_M(n) = \max\{\text{Space}_M(x) \mid x \in \Sigma^n\}\)

Definiere \(\text{Time}_M(n)\)

\(\text{Time}_M(n) = \max\{\text{Time}_M(x) \mid x \in \Sigma^n\}\)

Welche Inklusionen halten und sind mehr oder weniger tight?

SPACE(s(n)) \in U TIME(c^s(n))

TIME(s(n)) \in U SPACE(c^s(n))

TIME(t(n)) \in SPACE(t(n))

NTIME(t(n)) \subseteq NSPACE(t(n))

NTIME(s(n)) \subseteq U NSPACE(c^s(n))

Welche Inklusionen halten und sind mehr oder weniger tight?

NTIME(t(n)) \subseteq NSPACE(t(n))

NSPACE(s(n)) \subseteq NTIME(s(n))

NSPACE(s(n)) \subseteq U NTIME(c^s(n))

TIME(t(n)) \subseteq NTIME(t(n))

SPACE(s(n)) \subseteq NTIME(s(n))

Welche Inklusionen halten und sind einigermassen tight?

NTIME(s(n) \subseteq U TIME(c^s(n))

TIME(s(n)) \subseteq U NTIME(c^s(n))

SPACE(t(n)) \subseteq NSPACE(t(n))

NSPACE(s(n)) \subseteq U TIME(c^s(n))

SPACE(s(n)) \subseteq NSPACE(s(n)^2)

Welche Inklusionen halten und sind eingiermassen tight?

NSPACE(s(n)) \subseteq SPACE(s(n)^2)

NPSPACE \subseteq EXPTIME

EXPTIME\subseteq NPSPACE

NSPACE(s(n)) \subseteq U TIME(c^s(n))

SPACE(s(n)) \subseteq TIME(s(n))

Wie wird TIME(t(n)) \subseteq SPACE(t(n)) bewiesen?

Es macht keinen Sinn mehr Speicher zu benötigen als Zeitschritte zu haben, da diese Speicherzellen gar nicht innerhalb der Zeit erreicht werden könnnten.

Wie beweisst man SPACE(s(n)) \subseteq U TIME(c^s(n))?

Ex gilt |InKonf_M(n)| <= c^s(n).

Falls sich zwei innere Konfigurationen wiederholen sollten, macht es keinen Sinn, weiter zu arbeiten.

Nach d * c^s(n) Zeitschritten wurden also alle inneren Konfigurationen besucht und es macht keinen Sinn, länger zu arbeiten als TIME(c^s(n))