Я хотел бы знать об истории этих двух терминов: « эффективный », « выполнимый ».
Кто использовал их в отношении вычислений / алгоритмов в первый раз? (в современном понимании этих терминов, т.е. 20-го века). Как они стали мейнстримом? Как эти два термина начали использоваться как синонимы?
Я знаю, что Кобхем использовал термин «выполнимый» в формулировке своего тезиса, связанного с вычисляемостью за полиномиальное время. Но есть ли более ранняя ссылка? Кажется, в письме Годеля фон Нейману нет явной ссылки на эти термины . Я не смог найти ни одной связанной статьи до 1960 года (используя Google Scholar ).
Другим интересным моментом является то, что заголовок статьи Кобхэма 1965 года «Внутренняя сложность вычислений функций». Когда «вычислительная сложность» заменила «вычислительную сложность»?
Еще одна фраза, которую нужно рассмотреть, - «точно решаемо», которая взята из статистической физики и также соответствует нашим современным представлениям об эффективности / выполнимости. Введение в этой статье содержит хорошее историческое описание этой фразы со многими ссылками.
источник
Это не совсем то, что вы просили, но это слишком долго для комментария.
Самая старая явная ссылка, которую я знаю о алгоритме, который не может быть реализован, содержится в « Воспоминании об условно-досрочном освобождении» Эвариста Галуа , написанном в 1830 году:
Хотя верно, что алгоритм Галуа не работает за полиномиальное время, Галуа явно имел в виду нечто гораздо менее точное. Это также самая старая из известных мне ссылок, в которой говорится о существовании самого существенного алгоритма.
Как упоминает Ниль де Бодрап в комментариях, Гаусс уже обсуждал (не) эффективность алгоритмов для тестирования простоты в своей книге «Disquisitiones Arithmeticae» 1801 года , почти за 30 лет до Галуа. Для полноты вот соответствующий отрывок из статьи 329:
источник
Изменить: Ответ переписан
Как это стало мейнстримом? вероятно, распространяя идею сравнения нового исследования с более старым с точки зрения производительности, с предположением, что создание новых идей является более трудным.
источник