Участник:USSRocker/PSPACE in EXPTIME — Бойко Дмитрий, 175. — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
\begin{document}
 
\begin{document}
 
Пусть язык $L$ разрешим некоторой ДМТ $M$ с пространственной сложностью
 
Пусть язык $L$ разрешим некоторой ДМТ $M$ с пространственной сложностью
$f(n)$, где $f(n)\geq n$. $M$ может посетить максимум $f(n)2^{O(f(n))}$
+
$f(n)$, где $f(n) = {O(n^c)}, c = const$. $M$ может посетить максимум $f(n)2^{O(f(n))}$
 
конфигураций, так как:
 
конфигураций, так как:
  
Строка 21: Строка 21:
  
 
Получается, что $M$ работает за $f(n)2^{O(f(n))}$ операций. Значит,
 
Получается, что $M$ работает за $f(n)2^{O(f(n))}$ операций. Значит,
$SPACE(f(n))\subseteq TIME(2^{O(f(n))})$, отсюда, $PSPACE\subseteq EXPTIME$.  
+
 
 +
$DSPACE(f(n))\subseteq DTIME(2^{O(f(n))})$,  
 +
отсюда,  
 +
$DSPACE({O(n^c)})\subseteq DTIME(2^{O(n^c)})$,
 +
в итоге, в силу произвольности выбора $c$,
 +
$PSPACE\subseteq EXPTIME$.  
  
  
 
\end{document}
 
\end{document}
 
<\latex>
 
<\latex>

Версия 01:30, 28 мая 2014

Докажите, что .

Дмитрий Бойко, 175