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

Концепция в теории сложности

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

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

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

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

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

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

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

Примеры

Все обычно используемые функции f ( n ) (такие как n , n ^k , 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 .

^ abc Goldreich, Oded (2008). Computational Complexity: A Conceptual Perspective . Cambridge University Press. стр. 130, 139. ISBN 978-0-521-88473-0.
^ ab Homer, Steven; Selman, Alan L. (2011). Computability and Complexity Theory (Второе изд.). Springer. ISBN 978-1-4614-0681-5.
^ Балькасар, Хосе Луис; Диас, Хосеп; Габарро, Хоаким (1988). Структурная сложность I. Спрингер-Верлаг. ISBN 3-540-18622-0.

[:0-1] Goldreich, Oded (2008). Computational Complexity: A Conceptual Perspective . Cambridge University Press. стр. 130, 139. ISBN 978-0-521-88473-0.

[:2-2] Homer, Steven; Selman, Alan L. (2011). Computability and Complexity Theory (Второе изд.). Springer. ISBN 978-1-4614-0681-5.

[3] Балькасар, Хосе Луис; Диас, Хосеп; Габарро, Хоаким (1988). Структурная сложность I. Спрингер-Верлаг. ISBN 3-540-18622-0.