Кто ввел недетерминированные вычисления?

У меня есть два исторических вопроса:

Кто первым описал недетерминированные вычисления?

Я знаю, что Кук описал NP-полные проблемы, и что Эдмондс предложил, чтобы P-алгоритмы были "эффективными" или "хорошими" алгоритмами.

Я искал эту статью в Википедии и пролистал «О вычислительной сложности алгоритмов», но не смог найти никакой ссылки на то, когда недетерминированные вычисления впервые обсуждались.

Какая была первая ссылка на класс NP? Это была бумага Кука 1971 года?

Я всегда видел понятие недетерминизма в вычислениях, приписываемое Майклу Рабину и Дане Скотт. Они определили недетерминированные конечные автоматы в своей знаменитой статье « Конечные автоматы и проблемы их решения» , 1959. Цитирование премии Тьюринга Рабина также предполагает, что Рабин и Скотт представили недетерминированные машины.

Вот что Одифредди говорит по этому вопросу:

«Наша модель машины Тьюринга является детерминированной в том смысле, что инструкции должны быть непротиворечивыми (не более одного из них применимы в любой конкретной ситуации). Рандомизирующие элементы в вычислительных устройствах были впервые представлены Шенноном [1948] и Де Леу, Мур, Шеннон и Шапиро [1956]. Существуют в основном две модели: недетерминированные машины Тьюринга ведут себя в неоднозначной ситуации, когда могут применяться конфликтующие инструкции, случайным образом выбирая одну из них: их вычислительную мощность, по крайней мере, для 0, 1-значные функции (наборы) не превышают мощности детерминированных. Вероятностные машины отличаются от недетерминированных тем, что следующее состояние имеет вероятность, и, следовательно, конфликтующие инструкции не имеют такой же возможности быть выбранной машиной ".
[П. Одифредди, Классическая теория рекурсии, Vol. 1, стр. 50]

Обратите внимание, что понятие недетерминизма в смысле «существует + верификатор» существовало в теории вычислимости задолго до теории сложности, например , нормальной формы Клини , арифметической иерархии . Другие модели вычислений, такие как постканонические системы (известные как минимум с 1943 года) и грамматики, также являются недетерминированными. Я думаю, что можно даже подтолкнуть понятие ко времени эпсилонного исчисления Гильберта и операторов выбора.

Про NP я спросил Стива Кука. Название NP для класса недетерминированных вычислимых задач за полиномиальное время было введено Ричардом Карпом в его знаменитой статье 1972 года. Кук ссылается на класс недетерминированных вычислимых задач машины Тьюринга за полиномиальное время в своей знаменитой статье 1971 года, которая определяет полиномиальные сокращения времени и показывает, что существуют полные проблемы, но без указания имени для класса.

До его работы не было большого интереса к задачам, вычисляемым за полиномиальное время недетерминированными машинами Тьюринга, только после того, как статья Карпа показала, что в NP так много естественных проблем. После статьи Кука некоторые заинтересовались, особенно двое, кто заинтересовался на раннем этапе (до того, как вышла статья Карпа), были Майкл Рабин и Аллан Бородин .

Статья Карпа 1972 года удивила людей, показав, насколько всепроникающая NP-полнота входит в число естественных проблем.

Рабин и Скотт представили недетерминированные конечные автоматы в своей исследовательской работе, опубликованной в журнале IBM, апрель 1959 года. В статье они упоминали:

мы приняли еще более простую форму определения, избавившись от сложной выходной функции, и наши машины просто дают ответы «да» или «нет». Это также использовалось Myhill, но наши обобщения на «недетерминированные», «двусторонние» и «многолентные» машины кажутся новыми .

Весь документ можно посмотреть здесь: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf