Рабина «Степень сложности вычисления функции и частичное упорядочение рекурсивных множеств»

Я ищу:

Майкл О. Рабин, «Степень сложности вычисления функции и частичное упорядочение рекурсивных множеств», Еврейский университет, Иерусалим, 1960

Резюме:

«Мы пытаемся измерить объем работы, свойственный задаче вычисления заданной вычислимой (рекурсивной) функции. Представлено и изучено понятие степени сложности вычислений. Понятие инвариантно в том смысле, что оно не зависит от идеализированных компьютеров (машин Тьюринга), используемых для вычисления рассматриваемых функций. Применяются для классификации решаемых задач решения (рекурсивных множеств) по относительной сложности ».

Я не смог найти копию онлайн или в нашей библиотеке.

cc.complexity-theory reference-request ho.history-overview Кава
источник

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

Мухаммед Аль-Туркистани

Я надеюсь, что они хранят физическую копию в Еврейском университете ...

Yuval Filmus

Комментарий, не относящийся (непосредственно) к ФП: законно ли собирать онлайн-хранилище старых (я не знаю, сколько времени считается старым) тезисов / диссертаций и разрешать свободный доступ? По многим причинам, новые обычно легко получить.

Исинь Цао

Комментарии @YixinCao не подходят для того, чтобы задавать новые вопросы. Вы можете оставить вопрос по Академии .

Каве

PS: оказывается, это не тезис Рабина. Его диссертация по Википедии - «Рекурсивная неразрешимость групповых теоретических задач», 1957 г.

Каве,

Ответы:

Есть две ссудные копии в Национальной библиотеке Израиля.

Вот отсканированная копия .

Юваль Фильмус
источник

Ницца. Это печатные копии? Они предлагают версию PDF?

Мухаммед Аль-Туркистани

Жесткие копии. Но, возможно, они будут сканировать их по требованию. Я, вероятно, могу получить физическую копию самостоятельно, хотя я не собираюсь сканировать все это самостоятельно ...

Yuval Filmus

Спасибо, Юваль. Я надеюсь, что у кого-то есть отсканированная копия (учитывая, что это одна из основополагающих ссылок теории сложности).

Каве

@Kaveh: это одна из основополагающих ссылок? Я никогда не видел его привели ... У меня есть скан Рабин «Математическая теория автоматов» , которая является одним из трех работ часто цитируемых за то , что ввели понятие Р (и которые я поэтому делать рассмотреть основополагающим). Дай мне знать, если тебе понравится.

Джошуа Грохов

@ Джош, я видел, как это цитировалось вместе с Кобхэмом, Эдмондсом, Хартманисом и Стернсом как первые статьи, в которых говорится о том, что сейчас называется теорией вычислительной сложности. К счастью, у Стива есть копия тезиса Рабина, и он сказал, что отсканирует и разместит его в Интернете.

Каве