Конструктивная функция
В теории сложности — конструируемая по времени функция это функция f от натуральных чисел к натуральным числам, обладающая тем свойством, что f ( n ) может быть построена из n с помощью машины Тьюринга за время порядка f ( n ). Цель такого определения — исключить функции, которые не обеспечивают верхнюю границу времени выполнения некоторой машины Тьюринга. [1]
Конструируемые во времени определения
[ редактировать ]Существует два разных определения конструируемой во времени функции. В первом определении функция f называется конструируемой по времени, если существует целое положительное число n 0 и машина Тьюринга M , которая, учитывая строку 1 н состоящий из n единиц, останавливается ровно через f ( n ) шагов для всех n ≥ n 0 . Во втором определении функция f называется конструируемой во времени, если существует машина Тьюринга M , которая по заданной строке 1 н , выводит двоичное представление f ( n ) за время O ( f ( n )) (вместо этого можно использовать унарное представление, поскольку они могут быть взаимно преобразованы за время O ( f ( n ))). [1]
Существует также понятие полностью конструируемой во времени функции. Функция f называется полностью конструируемой во времени, если существует машина Тьюринга M , которая для строки 1 н состоящий из n единиц, останавливается ровно через f ( n ) шагов. [2] Это определение немного менее общее, чем первые два, но для большинства приложений можно использовать любое определение. [3]
Определения, конструируемые в пространстве
[ редактировать ]Аналогично, функция f является конструируемой в пространстве, если существует целое положительное число n 0 и машина Тьюринга M , которая, учитывая строку 1 н состоящий из n единиц, останавливается после использования ровно f ( n ) ячеек для всех n ≥ n 0 . Эквивалентно, функция f является пространственно-конструируемой, если существует машина Тьюринга M , которая, учитывая строку 1 н состоящий из n единиц, выводит двоичное (или унарное) представление f ( n ), используя только O ( f ( n )). пространство [1]
Кроме того, функция f полностью конструируема в пространстве, если существует машина Тьюринга M , которая, учитывая строку 1 н состоящий из n единиц, останавливается после использования ровно f ( n ) ячеек. [2]
Примеры
[ редактировать ]Все часто используемые функции f ( n ) (такие как n , n к , 2 н ) конструируемы во времени и пространстве, пока f ( n ) равна по крайней мере cn для константы c > 0. Никакая функция, равная o ( n ), не может быть конструируема во времени, если она в конечном итоге не является постоянной, поскольку недостаточно время прочитать весь ввод. Однако — пространственно-конструируемая функция.
Приложения
[ редактировать ]Конструируемые по времени функции используются в результатах теории сложности, таких как теорема об иерархии времени . Они важны, поскольку теорема об иерархии времени опирается на машины Тьюринга, которые должны за время O ( f ( n )) определить, сделал ли алгоритм больше, чем f ( n ) шагов. Это, конечно, невозможно без возможности вычислить f ( n ) за это время. Такие результаты обычно верны для всех естественных функций f , но не обязательно верны для искусственно созданных f . Чтобы их точно сформулировать, необходимо иметь точное определение натуральной функции f, для которой теорема верна. Для такого определения часто используются конструируемые во времени функции.
Пространственно-конструируемые функции используются аналогично, например, в теореме о пространственной иерархии .
Ссылки
[ редактировать ]Эта статья включает в себя материалы из сайта Constructible на PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .
- ^ Перейти обратно: а б с Гольдрейх, Одед (2008). Вычислительная сложность: концептуальная перспектива . Издательство Кембриджского университета. стр. 130, 139. ISBN. 978-0-521-88473-0 .
- ^ Перейти обратно: а б Гомер, Стивен; Селман, Алан Л. (2011). Теория вычислимости и сложности (второе изд.). Спрингер. ISBN 978-1-4614-0681-5 .
- ^ Балькасар, Хосе Луис; Диас, Джозеф; Габарро, Хоаким (1988). Структурная сложность I. Спрингер-Верлаг. ISBN 3-540-18622-0 .