Происхождение терминов «эффективный» и «выполнимый» расчет / алгоритм

13

Я хотел бы знать об истории этих двух терминов: « эффективный », « выполнимый ».

Кто использовал их в отношении вычислений / алгоритмов в первый раз? (в современном понимании этих терминов, т.е. 20-го века). Как они стали мейнстримом? Как эти два термина начали использоваться как синонимы?

Я знаю, что Кобхем использовал термин «выполнимый» в формулировке своего тезиса, связанного с вычисляемостью за полиномиальное время. Но есть ли более ранняя ссылка? Кажется, в письме Годеля фон Нейману нет явной ссылки на эти термины . Я не смог найти ни одной связанной статьи до 1960 года (используя Google Scholar ).

Другим интересным моментом является то, что заголовок статьи Кобхэма 1965 года «Внутренняя сложность вычислений функций». Когда «вычислительная сложность» заменила «вычислительную сложность»?

Кава
источник

Ответы:

11

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

«Вычислительная сложность» - более интересный термин. С помощью MathSciNet я обнаружил, что Юрис Хартманис, похоже, был первым, кто популяризировал его. Знаменитая статья 1965 года Хартманиса и Стернса использует этот термин в названии, но еще до этого в математическом обзоре Хартманиса к статье Майкла Рабина «Вычисления в реальном времени» ( Israel J. Math. 1 (1963), 203–211) говорится:

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

Обратите внимание, что сам Рабин не использует термин «вычислительная сложность» в этой статье.

MathSciNet также обнаруживает пару предыдущих обзоров, в которых используется термин «вычислительная сложность», но они кажутся спонтанными и случайными.

Тимоти Чоу
источник
Спасибо, я думаю, что это отвечает на мой вопрос о «вычислительной сложности». (Я хотел бы подождать еще несколько дней, чтобы узнать, может ли кто-нибудь предоставить некоторую информацию о первых двух сроках.)
Kaveh
5

Еще одна фраза, которую нужно рассмотреть, - «точно решаемо», которая взята из статистической физики и также соответствует нашим современным представлениям об эффективности / выполнимости. Введение в этой статье содержит хорошее историческое описание этой фразы со многими ссылками.

Тайсон Уильямс
источник
Спасибо Тайсон, это похоже на интересную статью (но, похоже, не отвечает на мои вопросы).
Каве
3

Это не совсем то, что вы просили, но это слишком долго для комментария.

Самая старая явная ссылка, которую я знаю о алгоритме, который не может быть реализован, содержится в « Воспоминании об условно-досрочном освобождении» Эвариста Галуа , написанном в 1830 году:

Если вы не согласны с этим, вы не согласны ни с чем, в сущности, с другой стороны, без сомнений, с точки зрения права голоса. зарядное устройство. En un mot les calculs не представляется практически невозможным.

[Теперь, если вы дадите мне уравнение, которое вы выбрали по своему усмотрению, и вы хотите знать, разрешимо ли оно радикалами, мне нужно только указать вам метод, необходимый для ответа на ваш вопрос, не желая самому или кто-нибудь другой это сделает. Одним словом, расчеты нецелесообразны .]

Хотя верно, что алгоритм Галуа не работает за полиномиальное время, Галуа явно имел в виду нечто гораздо менее точное. Это также самая старая из известных мне ссылок, в которой говорится о существовании самого существенного алгоритма.


Как упоминает Ниль де Бодрап в комментариях, Гаусс уже обсуждал (не) эффективность алгоритмов для тестирования простоты в своей книге «Disquisitiones Arithmeticae» 1801 года , почти за 30 лет до Галуа. Для полноты вот соответствующий отрывок из статьи 329:

Nihilominus fateri oportet, Omnes methodos hucusque prolata Vel объявление казус Влада speciales restrictas езз, Vel ТАМ operosas и др prolixas , у РМКО про Numeris talibus, кви tabularum Варис Меритис constructarum Limites не excedunt, то есть про quibus methodi artificiales supervacuae Сюнт, calculatoris Etiam exercitati patientiam fatigent, ad maiores autem plerumque vix Applicari possint. ... Ceterum in problemmatis natura fundatum est, ut Methodi quaecunqueконтинуо пролисиорес уклончиво, quo maiores sunt Numberri, ad quos заявитель; attamen про methodis sequentibus difficultates perlente increscunt, Numerique е Septem, octos Vel ADEO adhuc Pluribus figuris constantes praesertim за secundam Felici зетрег successu tractati fuerunt, omnique celeritate, Квам про tantis Numeris exspectare aequum Эст, кви Secundum Omnes methodos hactenus Notas Laborem, Etiam calculatori indefatigabili непереносимость, требуется.

[Тем не менее, мы должны признать, что все методы, которые были предложены до сих пор, либо ограничены очень особыми случаями, либо настолько трудоемки и распространены, что даже для чисел, которые не превышают пределы таблиц, построенных оценочными людьми, то есть для чисел, которые не Требуются гениальные методы, они испытывают терпение даже самого опытного калькулятора. И эти методы вряд ли можно использовать для больших чисел. ... Это в природе проблемы, что любойметод станет более распространенным, поскольку числа, к которым он применяется, становятся больше. Тем не менее, в следующих методах трудности увеличиваются довольно медленно, и числа с семью, восемью или даже более цифрами обрабатывались с успехом и скоростью, превосходящей ожидания, особенно вторым методом. Ранее известные методы потребовали бы непереносимого труда даже для самого неутомимого калькулятора .]

Jeffε
источник
2
Был также ответ на другую тему , о самых старых проблемах открытого исследования, в которых Гаусс жаловался в своей книге « Disquitiones Arithmeticae» 1801 года, что все методы, известные в то время для тестирования простоты, были очень «трудоемкими и распространенными».
Ниль де Бодрап,
Zp
п
-1

Изменить: Ответ переписан

Как это стало мейнстримом? вероятно, распространяя идею сравнения нового исследования с более старым с точки зрения производительности, с предположением, что создание новых идей является более трудным.

labotsirc
источник
Я ищу фактическую историю этих терминов, а не их объяснение. Это не ответ на мой вопрос.
Каве
Я не могу ответить, кто впервые использовал эти термины в CS, мой ответ был более ориентирован на ваш второй вопрос о том, почему он получил широкое распространение.
labotsirc
Спасибо, но я не спрашиваю «почему», я спрашиваю «как» (то есть история).
Каве
я переписал ответ, это все, что я знаю + предположения. С уважением, Кристобаль.
labotsirc
1
Спасибо, но, как я уже сказал, я ищу реальную историю, а не вероятные теории об этом. Я ищу ранние ссылки / документы / ... которые использовали термины и помогли стать мейнстримом.
Каве