Matematické Fórum

Hertas · 09. 06. 2016 16:08 — Editoval Hertas (09. 06. 2016 16:32)

Ahoj,

teorii složitosti zrovna dvakrát nehovím, nehledě na to, že přednášky i skripta nepatří mezi ty nejlepší se kterými jsem se setkal. Nicméně k problému:

Dokažte, že $DTime(2^n) \subset DTime(n2^n)$ . Návod - použijte funkce $f(n)=2^n$ a $f(n)=n + 2^n$

Na vysvětlenou: jestli jsem to dobře pochopil (nemám k dispozici rigorózní matematickou definici), tak DTime vyjadřuje časovou složitost výpočtu (konstruovatelnosti) funkce na deterministickém Turingově stroji.

Pravděpodobně by se měla použít tato věta:
Nechť $t_1, t_2, f$ jsou časově konstruovatelné funkce, $f(n) > n + 1 \wedge \exists \varepsilon >0, t_1(n),t_2(n) > (1+\varepsilon)n$ , pak:
$DTime(t_1(n)) \subseteq DTime(t_2(n)) \Rightarrow DTime(t_1(f(n))) \subseteq DTime(t_2(f(n)))$

Matematické Fórum

#1 09. 06. 2016 16:08 — Editoval Hertas (09. 06. 2016 16:32)

Teorie složitosti

Zápatí