В теории сложности , А времени конструктивны функция является функцией F от натуральных чисел до натуральных чисел со свойством , что е ( п ) можно построить из п на машине Тьюринга в момент заказа F ( п ). Цель такого определения - исключить функции, которые не обеспечивают верхнюю границу времени выполнения некоторой машины Тьюринга. [1]
Конструируемые во времени определения
Есть два разных определения функции, конструируемой во времени. В первом определении функция f называется конструируемой по времени, если существует натуральное число n 0 и машина Тьюринга M, которая для строки 1 n, состоящей из n единиц, останавливается ровно после f ( n ) шагов для всех n ≥ n. 0 . Во втором определении функция f называется конструируемой во времени, если существует машина Тьюринга M, которая, учитывая строку 1 n , выводит двоичное представление f ( n ) за время O ( f ( n )) (унарное представление может использоваться вместо этого, поскольку они могут быть взаимно преобразованы за время O ( f ( n ))). [1]
Также существует понятие полностью конструируемой во времени функции. Функция f называется полностью конструктивной по времени, если существует машина Тьюринга M, которая для строки 1 n, состоящей из n единиц, останавливается ровно после f ( n ) шагов. Это определение немного менее общее, чем первые два, но для большинства приложений можно использовать любое определение [ необходима ссылка ] .
Пространственно-конструктивные определения
Точно так же функция f является пространственно-конструктивной, если существует положительное целое число n 0 и машина Тьюринга M, которая для строки 1 n, состоящей из n единиц, останавливается после использования ровно f ( n ) ячеек для всех n ≥ n 0 . Эквивалентно, функция f является пространственно-конструктивной, если существует машина Тьюринга M, которая, учитывая строку 1 n, состоящую из n единиц, выводит двоичное (или унарное) представление f ( n ), используя только O ( f ( n )) космос. [1]
Кроме того , функция F является полностью пространственно-конструктивны , если существует машина Тьюринга М , который, учитывая строку 1 п , состоящее из п из них, после того, как с помощью остановок точно е ( п ) клеток [ править ] .
Примеры
Все часто используемые функции f ( n ) (такие как n , n k , 2 n ) конструктивны во времени и пространстве, пока f ( n ) не меньше cn для константы c > 0. Нет функции, которая была бы o ( n ) может быть конструируемым по времени, если он в конечном итоге не станет постоянным, поскольку времени для чтения всего ввода недостаточно. Тем не мение, является пространственно-конструктивной функцией.
Приложения
Функции, построенные по времени, используются в результатах теории сложности, таких как теорема об иерархии времени . Они важны, потому что теорема о временной иерархии основана на машинах Тьюринга, которые должны определить за время O ( f ( n )), сделал ли алгоритм больше, чем f ( n ) шагов. Это, конечно, невозможно без возможности вычислить f ( n ) за это время. Такие результаты обычно верны для всех естественных функций f, но не обязательно верны для искусственно построенных функций f . Чтобы сформулировать их точно, необходимо иметь точное определение естественной функции f, для которой теорема верна. Для такого определения часто используются конструируемые во времени функции.
Аналогично используются пространственно-конструктивные функции, например, в теореме пространственной иерархии .
В эту статью включены материалы из материала для построения на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .