Какие классические статьи из области теории рекурсии теории сложности?

Две статьи, которые я бы включил:

Д. Козен, "Индексация субрекурсивных классов" , STOC, 1978.
Р. Лэднер, "О структуре полиномиальной временной сводимости" , JACM, 1975.

cc.complexity-theory lo.logic computability big-list structural-complexity Kaveh
источник

это должен быть CW

Суреш Венкат

Я согласен с Сурешем. Просто добавлю: этот вопрос, вероятно, можно перефразировать таким образом, чтобы не нужно было вики сообщества (например, «Что я должен прочитать, когда начинаю с теории рекурсии?»), Так что одного ответа может быть достаточно. Это в настоящее время слишком открыто.

Шейн

мы должны использовать это как пример для FAQ

Suresh Venkat

Ответы:

Хайек П. Арифметическая иерархия и сложность вычислений . ТМФ. Комп. Sci. 8 (2): 227-237, 1979. Началось изучение сложностей наборов индексов (где их "сложности" часто лежат где-то в арифметической иерархии; см. Этот ответ на другой вопрос .)

Что касается изучения степеней полиномиального времени (buzzword = "теория степеней полиномиального времени", для будущих поисков), я бы сказал, что эти работы представляют интерес (некоторые из них основаны на методике Ладнера):

Гомер С. Минимальные степени для полиномиальных сводимостей . J. ACM 34 (2): 480-491, 1987.
Schöning, U. Минимальные пары для P . ТМФ. Комп. Sci. 31: 41-48, 1984.
Дауни Р. Нондиамондовские теоремы для полиномиальной сводимости по времени . Журнал компьютерных и системных наук 45 (3): 385-195, 1992.
Дауни Р. и Фортноу Л. Равномерно жесткие языки . ТМФ. Комп. Sci. 298 (2): 303-315, 2003.
Феннер С., Гомер С., Приум Р. и Шефер М. Гиперполиномиальные иерархии и полиномиальный скачок . ТМФ. Комп. Sci. 262: 241-256, 2001.

Вероятно, прямой и обратный поиск ссылок найдет еще несколько статей в той же области (хотя это не такая большая область!).

Джошуа Грохов
источник