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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 14 промежуточных версий этого же участника)
Строка 7: Строка 7:
 
</latex>
 
</latex>
  
[[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>
+

Текущая версия на 06:50, 4 мая 2023