Введение

цифровые репозитории

В теории вычислительной сложности DSPACE или SPACE — это вычислительный ресурс, описывающий объем памяти, необходимой детерминированной машине Тьюринга. Он представляет собой общий объем памяти, который потребовался бы "обычному" физическому компьютеру для решения конкретной вычислительной задачи с использованием заданного алгоритма.

Модели машин

DSPACE традиционно измеряется на детерминированной машине Тьюринга. Несколько важных классов сложности по памяти являются сублинейными, то есть меньше размера входных данных. Таким образом, "взимание платы" с алгоритма за размер входных или выходных данных не отражает истинный объем используемой памяти. Это решается путем определения многоленточной машины Тьюринга с входом и выходом, которая представляет собой стандартную многоленточную машину Тьюринга, за исключением того, что на входную ленту нельзя производить запись, а с выходной ленты нельзя производить чтение. Это позволяет определить более мелкие классы памяти, такие как L (логарифмическая память), с точки зрения объема памяти, используемого всеми рабочими лентами (исключая специальные входную и выходную ленты). Поскольку множество символов можно упаковать в один, выбирая подходящую степень алфавита, для всех c ≥ 1 и f, таких что f(n) ≥ 1, класс языков, распознаваемых в пространстве c f(n), совпадает с классом языков, распознаваемых в пространстве f(n). Это оправдывает использование нотации "большое O" в определении.

Отношения с другими классами сложности

DSPACE является детерминированным аналогом NSPACE, класса пространства памяти на недетерминированной машине Тьюринга. По теореме Савича, имеем следующее соотношение между NTIME и DSPACE. Для любой конструктивной по времени функции t(n) справедливо:

.