Неявная вычислительная сложность

Неявная вычислительная сложность ( ICC ) — это подраздел теории вычислительной сложности , который характеризует алгоритмы ограничениями на способ их построения без ссылки на конкретную базовую модель машины или на явные ограничения вычислительных ресурсов, в отличие от традиционной теории сложности. ICC был разработан в 1990-х годах и использует методы теории доказательств , субструктурной логики , теории моделей и теории рекурсии для доказательства границ выразительных возможностей формальных языков высокого уровня. ICC также занимается практической реализацией языков функционального программирования , языковых инструментов и теории типов , которые могут контролировать использование ресурсов программ в формально проверяемом смысле.

Неявные представления полиномиального времени

Важные классы сложности множеств, разрешимых за полиномиальное время (класс P ) и функций, вычислимых за полиномиальное время ( FP ), получили большое внимание и обладают несколькими неявными представлениями. Далее следуют два примера.

Программы без минусов

Джонс определил язык программирования, который может решать задачи решения, где входными данными является двоичная строка, и показал, что проблема может быть решена на этом языке тогда и только тогда, когда она находится в P. Кратко этот язык можно описать следующим образом. Он получает входные данные в виде списка битов. В нем есть переменные, которые могут указывать на список и изменяться с помощью операции «хвост», чтобы они могли двигаться вперед по списку. Он может определять рекурсивные функции , но не имеет функций высшего порядка . Важно отметить, что в нем нет конструкторов типов данных (отсюда и название cons-free ): входной список — это единственная структура данных во всей программе. Отсутствие конструкторов ограничивает вычислительную мощность языка, поэтому неудивительно, что он не может решить все разрешимые проблемы, но интерес к нему с точки зрения неявной вычислительной сложности заключается в том, что он может решать именно P, и это не зависит от время выполнения программ, которое может быть экспоненциальным. Интересно, что Джонс также показал, что если к языку добавить недетерминизм (как в Недетерминированная машина Тьюринга ), класс задач, который можно принять, по-прежнему P.

Функциональные алгебры с рекурсией в обозначениях

Беллантони и Кук показал, что определенный класс функций совпадает с ФП. Это функции, которые, как и примитивно-рекурсивные функции , определяются набором базовых функций и операторов для создания новых функций из существующих. Вместо примитивной схемы рекурсии используется специальная схема рекурсии, как будет видно ниже, и, кроме того, аргументы функций разделены на два «сорта». Это обозначается разделением аргументов точкой с запятой: $f(x_{1},\dots ,x_{k};x_{k+1},\dots ,x_{k+n})$. Аргументы, следующие за точкой с запятой, называются безопасными (более интуитивно понятное имя может быть «защищенным»). Когда значение передается в безопасной позиции, ему не разрешается слишком сильно расти — обратите внимание на разницу между пунктами (3) и (4) ниже. Еще одно важное отличие от определения примитивно-рекурсивных функций заключается в том, что здесь аргументы рассматриваются как двоичные строки , и мы можем увеличить значение, добавив бит ( x 0 или x 1) в отличие от числовой функции-преемника ( x' ).

Вот список основных функций:

1. пустая строка : $\varepsilon$ (нулевая функция)
2. прогнозы : $$\pi _{i}^{k,n}(x_{1},\ldots ,x_{k};x_{k+1},\ldots ,x_{k+n})=x_{i},$$ для каждого $1\leq i\leq k+n$
3. обычные двоичные преемники : $$S_{i}(x;)=xi,\ i\in \{0,1\}$$
4. ограниченные безопасные двоичные преемники : $$S_{i}(z;x)=\left\{{\begin{array}{ll}xi&{\text{if }}|x|<|z|\\x&{\text{otherwise}}\end{array}}\right.$$
5. двоичный предшественник : $$P(;\varepsilon )=\varepsilon ,P(;xi)=x$$
6. числовой предшественник : $p(;\varepsilon )=\varepsilon ,\ p(;x')=x$
7. условно : $$Q(;\varepsilon ,y,z_{0},z_{1})=y,Q(;xi,y,z_{0},z_{1})=z_{i}$$
8. итоговый продукт : $\times (x,y;)=1^{|x|\times |y|}$.

Мы можем комбинировать функции для формирования новых, используя схему композиции и схему рекурсии. Данный $g,{\vec {r}},{\vec {s}}$, их предикативный состав , $f=g\circ ({\vec {r}};{\vec {s}})$ определяется $$f({\vec {x}};{\vec {y}})=g({\vec {r}}({\vec {x}};);{\vec {s}}({\vec {x}};{\vec {y}})).$$ Данный $g,h_{0},h_{1}$, предикативная рекурсия по схеме обозначений определяет функцию $f$ к $${\begin{aligned}f(\varepsilon ,{\vec {x}};{\vec {y}})&=g({\vec {x}};{\vec {y}}),\\f(zi,{\vec {x}};{\vec {y}})&=h_{i}(z,{\vec {x}};{\vec {y}},f(z,{\vec {x}};{\vec {y}})).\end{aligned}}$$ Это называется «рекурсия по записи», потому что при каждом рекурсивном вызове мы удаляем часть аргумента рекурсии, в отличие от рекурсии «по значению», которая идет от z до z -1.

Пример. Мы определяем функцию $r(x)$ который получает двоичную строку x и возвращает строку из 0 той же длины, что и x . Для удобства чтения мы опускаем вызовы функций проекции, которые технически необходимы для получения аргумента функции, например: $\pi _{1}^{1}(x)$ получить х в функции $g(x)$. $${\begin{aligned}g(x)&=f(x,x),{\text{where}}\\f(\varepsilon ,x;)&=\varepsilon ,\\f(zi,x;)&=S_{0}(x;f(z,x;)).\end{aligned}}$$ Обратите внимание, что нам нужно изначально сохранить копию x , чтобы иметь возможность применить ограниченный двоичный оператор-преемник в рекурсии.

Другие классы

Неявные представления были найдены для многих классов сложности, включая иерархия классов времени P, EXPTIME , 2-EXPTIME ,... и пространственных классов L , PSPACE , EXPSPACE ,... ; а также классы иерархии DTIME ( O ( n )), DSPACE ( O ( n )), DTIME ( $O(2^{n})$), ДСПЕЙС ( $O(2^{n})$),... . Для большинства классов известно несколько альтернативных представлений.