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

Версия 20:58, 14 декабря 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>