Конструктивная функция

В теории сложности — конструируемая по времени функция это функция f от натуральных чисел к натуральным числам, обладающая тем свойством, что f ( n ) может быть построена из n с помощью машины Тьюринга за время порядка f ( n ). Цель такого определения — исключить функции, которые не обеспечивают верхнюю границу времени выполнения некоторой машины Тьюринга.

Конструируемые во времени определения

Существует два разных определения конструируемой во времени функции. В первом определении функция f называется конструируемой по времени, если существует целое положительное число n ₀ и машина Тьюринга M , которая, учитывая строку 1 ^н состоящий из n единиц, останавливается ровно через f ( n ) шагов для всех n ≥ n ₀ . Во втором определении функция f называется конструируемой во времени, если существует машина Тьюринга M , которая по заданной строке 1 ^н , выводит двоичное представление f ( n ) за время O ( f ( n )) (вместо этого можно использовать унарное представление, поскольку они могут быть взаимно преобразованы за время O ( f ( n ))).

Существует также понятие полностью конструируемой во времени функции. Функция f называется полностью конструируемой во времени, если существует машина Тьюринга M , которая для строки 1 ^н состоящий из n единиц, останавливается ровно через f ( n ) шагов. Это определение немного менее общее, чем первые два, но для большинства приложений можно использовать любое определение.

Определения, конструируемые в пространстве

Аналогично, функция f является конструируемой в пространстве, если существует целое положительное число n ₀ и машина Тьюринга M , которая, учитывая строку 1 ^н состоящий из n единиц, останавливается после использования ровно f ( n ) ячеек для всех n ≥ n ₀ . Эквивалентно, функция f является пространственно-конструируемой, если существует машина Тьюринга M , которая, учитывая строку 1 ^н состоящий из n единиц, выводит двоичное (или унарное) представление f ( n ), используя только O ( f ( n )). пространство

Кроме того, функция f полностью конструируема в пространстве, если существует машина Тьюринга M , которая, учитывая строку 1 ^н состоящий из n единиц, останавливается после использования ровно f ( n ) ячеек.

Примеры

Все часто используемые функции f ( n ) (такие как n , n ^к , 2 ^н ) конструируемы во времени и пространстве, пока f ( n ) равна по крайней мере cn для константы c > 0. Никакая функция, равная o ( n ), не может быть конструируема во времени, если она в конечном итоге не является постоянной, поскольку недостаточно время прочитать весь ввод. Однако ⁠ $\log(n)$⁠ — пространственно-конструируемая функция.

Приложения

Конструируемые по времени функции используются в результатах теории сложности, таких как теорема об иерархии времени . Они важны, поскольку теорема об иерархии времени опирается на машины Тьюринга, которые должны за время O ( f ( n )) определить, сделал ли алгоритм больше, чем f ( n ) шагов. Это, конечно, невозможно без возможности вычислить f ( n ) за это время. Такие результаты обычно верны для всех естественных функций f , но не обязательно верны для искусственно созданных f . Чтобы их точно сформулировать, необходимо иметь точное определение натуральной функции f, для которой теорема верна. Для такого определения часто используются конструируемые во времени функции.

Пространственно-конструируемые функции используются аналогично, например, в теореме о пространственной иерархии .

Ссылки

Эта статья включает в себя материалы из сайта Constructible на PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .