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

Версия 12:39, 24 декабря 2014

@@ Строка 7: / Строка 7: @@
 </latex>
-[[Category:На проверку]]
+[[Category:Нерешенные задачи]]
+<!--Вообще-то, решения уже есть-->
-<latex>
-$L \in LOGSPACE$, если он распознается Машиной Тьюринга T, который использует O(log n) ячеек памяти.
-МТ работает за время не большее чем общеe число всех конфигураций, где конфигурация определяется состоянием ленты, состоянием МТ и положением головки.
-Количество состояний ленты = $E^{O(log n)}$ , где E - алфавит.
-Количество положений головки = O(log n).
-Количество состояний это константа.
-Следовательно, количество конфигураций = |Г| * $O(\log n) * E^{O(\log n)} = O(n^c)$
-\\(при больших шагов МТ,конфигурации будут повторяться, а это значит, что МТ зациклиться, а это противоречит тому что он разрешает данный язык )
-\\Получили, что МТ работает за время, не больше чем полином. Т. е. L \in P
-</latex>