Временная и пространственная сложность алгоритмов/Задачи/PSPACE in EXPTIME — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Докажите, что <m>PSPACE \subseteq EXPTIME </m>.
 
Докажите, что <m>PSPACE \subseteq EXPTIME </m>.
  
−
<latex>
 
−
\begin{document}
 
−
Пусть язык $L$ разрешим некоторой ДМТ $M$ с пространственной сложностью
 
−
$f(n)$, где $f(n)\geq n$. $M$ может посетить максимум $f(n)2^{O(f(n))}$
 
−
конфигураций, так как:
 
  
−
1. Головка $M$ может закончить работу на одной из $f(n)$ ячейках.
 
−
 
−
2. Язык $L$ является некоторым подмножеством $\Sigma^{*}$, где $\Sigma$
 
−
- некоторый конечный алфавит. Любой конечный алфавит мы можем отобразить
 
−
в язык, состоящий из 0 и 1, а затем перевести слова языка $L$ в двоичное
 
−
представление. Значит, мы будем считать, что машине $M$ подаётся
 
−
уже бинарный вариант задачи. Тогда и получается, что на ленте может
 
−
быть записано $2^{O(f(n))}$ слов из 0 и 1.
 
−
 
−
Получается, что $M$ работает за $f(n)2^{O(f(n))}$ операций. Значит,
 
−
$SPACE(f(n))\subseteq TIME(2^{O(f(n))})$, отсюда, $PSPACE\subseteq EXPTIME$.
 
−
 
−
 
−
\end{document}
 
−
<\latex>
 
  
 
[[Category:Нерешенные задачи]]
 
[[Category:Нерешенные задачи]]
 +
<<<<<<< ваша версия:
 +
||||||| старый текст:
 +
<!--Вообще-то, решения уже есть-->
 +
=======
 
[[Category:На проверку]]
 
[[Category:На проверку]]
 +
>>>>>>> (чужая версия)

Версия 11:24, 18 мая 2014

Докажите, что . <<<<<<< ваша версия: ||||||| старый текст:

=

>>>>>>> (чужая версия)

Источник — «https://discopal.ispras.ru/index.php?title=Временная_и_пространственная_сложность_алгоритмов/Задачи/PSPACE_in_EXPTIME&oldid=2989»