El origen de los términos cálculo / algoritmo "eficiente" y "factible"

Me gustaría saber sobre la historia de estos dos términos: " eficiente ", " factible ".

¿Quién los usó sobre computación / algoritmos la primera vez? (en el sentido moderno de estos términos, es decir, siglo XX). ¿Cómo se convirtieron en la corriente principal? ¿Cómo comenzaron a usarse estos dos términos como sinónimos?

Sé que Cobham usó el término "factible" en la declaración de su tesis que se asocia con la computabilidad del tiempo polinomial. ¿Pero hay una referencia anterior? No parece haber una referencia explícita a estos términos en la carta de Godel a von Neumann . No pude encontrar ningún artículo relacionado anterior a 1960 (usando Google Scholar ).

Otro punto interesante es que el título del artículo de Cobham de 1965 es "La dificultad computacional intrínseca de las funciones". ¿Cuándo reemplazó la "complejidad computacional" a la "dificultad computacional"?

No conozco los términos "eficiente" y "factible". Dado que estos términos aún hoy no tienen un significado técnico preciso, sospecho que la historia de su uso resultará turbia, al igual que la historia de la mayoría de las palabras en la mayoría de los idiomas es turbia.

"Complejidad computacional" es un término más interesante. Con la ayuda de MathSciNet, encuentro que Juris Hartmanis parece haber sido el primero en popularizarlo. El famoso artículo de 1965 de Hartmanis y Stearns usa el término en el título, pero incluso antes de eso, la Revisión matemática de Hartmanis del artículo " Cálculo en tiempo real" de Michael Rabin ( Israel J. Math. 1 (1963), 203–211) dice:

Este resultado es muy instructivo y aporta nuevas técnicas a la teoría emergente de la complejidad computacional de las secuencias y funciones recursivas. Esta teoría se ocupa principalmente de la clasificación de problemas computables por su grado de dificultad computacional, el estudio de las propiedades de estas clases de complejidad, su relación entre sí y su dependencia de los dispositivos informáticos (abstractos).

Tenga en cuenta que el propio Rabin no utiliza el término "complejidad computacional" en este documento.

MathSciNet también muestra un par de revisiones anteriores que usan el término "complejidad computacional", pero estos parecen ser eventos espontáneos y esporádicos.

Otra frase a considerar es "exactamente solucionable", que proviene de la física estadística y también se corresponde con nuestras nociones actuales de eficiente / factible. La introducción en este documento contiene una buena descripción histórica de esta frase con muchas referencias.

Esto no es exactamente lo que pediste, pero es demasiado largo para un comentario.

La referencia explícita más antigua que conozco a un algoritmo que no es factible se encuentra en Mévarire sur les condition of résolubilité des équations par radicaux , de Évariste Galois , escrito en 1830:

Si mainousnant vous me donnez une équation que vous aurez choisie à votre gré et que vous desirez connaître si elle est ou no soluble par radicaux, je n'aurais rien à y faire que de vous indicar le moyen de répondre à votre question, sans vouloir cargador ni moi ni personne de la faire. En un mot les calculs sont impracticables.

[Ahora, si me das una ecuación que hayas elegido a tu discreción y quieres saber si los radicales pueden resolverla o no, solo necesito indicarte el método necesario para responder a tu pregunta, sin querer hacerme o alguien más lo lleva a cabo. En una palabra, los cálculos no son prácticos .]

Aunque es cierto que el algoritmo de Galois no se ejecuta en tiempo polinómico, Galois claramente significaba algo mucho menos preciso. Esta es también la referencia más antigua que conozco que considera la mera existencia de un algoritmo significativo por derecho propio.

Como Niel de Beaudrap menciona en los comentarios, Gauss ya discutió la (in) eficiencia de los algoritmos para las pruebas de primalidad en sus 1801 Disquisitiones Arithmeticae , casi 30 años antes que Galois. Para completar, aquí está el pasaje relevante del artículo 329:

Nihilominus fateri oportet, omnes methodos hucusque prolata vel ad casus vlade speciales restrictas esse, vel tam operosas et prolixas , ut iam pro numeris talibus, qui tabularum a varis meritis constructarum limites non excedunt, es decir , pro quibus methodi artificial supervacuae sunt ejercitati fatigent, ad maiores autem plerumque vix aplicar. ... Ceterum in problematis natura fundatum est, ut methodi quaecunquecontinuo prolixiores evadant, quo maiores sunt numeri, ad quos solicitante; attamen pro methodis sequentibus difficultates perlente increscunt, numerique e septem, octos vel adeo adhuc pluribus figuris constantes praesertim per secundam felici sempre successu tractati fuerunt, omnique celeritate, quam pro tantis numeris exspectare aequum est, qui secthodoru memefutoumem, meme calculadora, notas intolerabilem, requirerent.

[Sin embargo, debemos confesar que todos los métodos que se han propuesto hasta ahora están restringidos a casos muy especiales o son tan laboriosos y prolíficos que incluso para números que no exceden los límites de las tablas construidas por hombres estimables, es decir , para números que no requieren métodos ingeniosos, prueban la paciencia incluso de la calculadora más practicada. Y estos métodos difícilmente pueden usarse para números más grandes. ... Es en la naturaleza del problema que cualquierEl método se volverá más prolijo a medida que los números a los que se aplica crezcan. Sin embargo, en los siguientes métodos las dificultades aumentan bastante lentamente, y los números con siete, ocho o incluso más dígitos se han manejado con éxito y velocidad más allá de lo esperado, especialmente por el segundo método. Las técnicas que se conocían anteriormente requerirían una mano de obra intolerable incluso para la calculadora más infatigable .]

Editar: Respuesta reescrita

¿Cómo se hizo mainstream? probablemente al difundir la idea de comparar nuevas investigaciones con las más antiguas en términos de rendimiento, con la suposición de que crear nuevas ideas es más difícil.