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

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 7: Строка 7:
 
</latex>
 
</latex>
  
[[Category:Нерешенные задачи]]
+
[[User:USSRocker|Дмитрий Бойко, 175]]
<!--Вообще-то, решения уже есть-->
+
 
 +
[[Категория:На проверку]]
 +
 
 +
<latex>
 +
\begin{document}
 +
Пусть язык $L$ разрешим некоторой ДМТ $M$ с пространственной сложностью
 +
$f(n)$, где $f(n) = {O(log 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))}$ операций. Значит,
 +
 
 +
$DSPACE(f(n))\subseteq DTIME(2^{O(f(n))})$,
 +
отсюда,
 +
$DSPACE({O(log n)})\subseteq DTIME(O(n^c)})$,
 +
где $c$ - константа, в итоге,
 +
$LOGSPACE\subseteq P$.
 +
 
 +
 
 +
\end{document}
 +
<\latex>

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

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