stringtranslate.com

Juris Hartmanis

Juris Hartmanis (5 de julio de 1928 - 29 de julio de 2022) fue un científico informático y teórico computacional estadounidense nacido en Letonia que, con Richard E. Stearns , recibió el premio ACM Turing de 1993 "en reconocimiento a su artículo fundamental que estableció las bases para el campo de la teoría de la complejidad computacional ".

Vida y carrera

Hartmanis nació en Letonia el 5 de julio de 1928. [2] Era hijo de Mārtiņš Hartmanis  [lv] , [3] un general del ejército letón, e Irma Marija Hartmane. Era el hermano menor de la poeta Astrid Ivask . Después de que la Unión Soviética ocupara Letonia en 1940 , Mārtiņš Hartmanis fue arrestado por los soviéticos y murió en una prisión. Más tarde, en la Segunda Guerra Mundial , la esposa y los hijos de Mārtiņš Hartmanis abandonaron Letonia en 1944 como refugiados, temiendo por su seguridad si la Unión Soviética se apoderaba de Letonia nuevamente. [6] [7]

Primero se mudaron a Alemania , donde Juris Hartmanis recibió el equivalente a una maestría en física de la Universidad de Marburg . Luego se mudó a los Estados Unidos , donde en 1951 obtuvo una maestría en matemáticas aplicadas en la Universidad de Kansas City (ahora conocida como Universidad de Missouri-Kansas City ) y en 1955 un doctorado. en matemáticas de Caltech bajo la supervisión de Robert P. Dilworth . [8] La Universidad de Missouri-Kansas City lo honró con un Doctorado Honorario en Letras Humanitarias en mayo de 1999. [9] Después de enseñar matemáticas en la Universidad de Cornell y la Universidad Estatal de Ohio , Hartmanis se unió al Laboratorio de Investigación de General Electric en 1958. Mientras estaba en General Electric, desarrolló muchos principios de la teoría de la complejidad computacional. [15] En 1965, se convirtió en profesor en la Universidad de Cornell. Fue uno de los fundadores y el primer presidente de su departamento de informática (que fue uno de los primeros departamentos de informática del mundo). [dieciséis]

Hartmanis contribuyó a los esfuerzos nacionales para avanzar en ciencias e ingeniería informática (CS&E) de muchas maneras. Lo más significativo es que presidió el estudio del Consejo Nacional de Investigación que dio lugar a la publicación de 1992 Computing the Future – A Broad Agenda for Computer Science and Engineering , [17] que hizo recomendaciones basadas en sus prioridades para sostener el esfuerzo central en CS&E, para ampliar el y mejorar la educación universitaria en CS&E. Fue subdirector de la Dirección de Ingeniería y Ciencias de la Información y Computación (CISE) de la Fundación Nacional de Ciencias (NSF) [18] de 1996 a 1998.

En 1989, Hartmanis fue elegido miembro de la Academia Nacional de Ingeniería por sus contribuciones fundamentales a la teoría de la complejidad computacional y a la investigación y educación en informática. Fue miembro de la Association for Computing Machinery y de la American Mathematical Society , [19] también miembro de la Academia Nacional de Ciencias . [20] También fue miembro extranjero de la Academia de Ciencias de Letonia , [21] que le otorgó su Gran Medalla  [lv] en 2001 por sus contribuciones a la informática. [22]

Hartmanis murió el 29 de julio de 2022. [23] [24] [25]

Complejidad computacional: contribuciones fundamentales

En 1993, Hartmanis y RE Stearns recibieron el premio más importante en informática, el Premio Turing . La cita dice: "En reconocimiento a su artículo fundamental que estableció las bases para el campo de la teoría de la complejidad computacional ". [26] Su artículo [13] definió la noción fundamental de una clase de Complejidad , una forma de clasificar problemas computacionales según el tiempo necesario para resolverlos. Luego demostraron una serie de resultados fundamentales, como el teorema de la jerarquía del tiempo . En su propia conferencia del Premio Turing, Richard M. Karp comenta que "es el artículo de 1965 de Juris Hartmanis y Richard Stearns el que marca el comienzo de la era moderna de la teoría de la complejidad". [27]

Con el primer ministro Lewis II, Hartmanis y Stearns también definieron clases de complejidad basadas en el uso del espacio y demostraron el primer teorema de la jerarquía espacial. [12] En el mismo año también demostraron [28] que todo lenguaje libre de contexto tiene una complejidad espacial determinista (log n) 2 , lo que contenía la idea esencial que condujo al teorema de Savitch sobre la complejidad espacial.

Hartmanis continuó haciendo importantes contribuciones al campo de la complejidad computacional durante décadas. Con Leonard Berman, demostró que todos los lenguajes naturales NP-completos son isomórficos en tiempo polinomial [29] y conjeturó que esto es válido para todos los conjuntos NP-completos. [30] Aunque la conjetura en sí permanece abierta, ha dado lugar a un gran conjunto de investigaciones sobre la estructura de conjuntos NP-completos, que culminaron en el teorema de Mahaney sobre la inexistencia de conjuntos NP-completos dispersos. [31] [32] [33] [34] Él y sus coautores también definieron la jerarquía booleana . [35] [36]

El artículo de Hartmanis de 1981 [14] ofrece una descripción personal de los avances en esta área y en la teoría de los autómatas y analiza las creencias y la filosofía subyacentes que guiaron su investigación. El libro escrito en honor a su 60 cumpleaños, [37] en particular, el capítulo de Stearns, [38] es un recurso valioso sobre la complejidad computacional.

A finales de la década de 1980, la exposición de Hartmanis [39] sobre una carta recién descubierta fechada el 20 de marzo de 1956 de Gödel a von Neumann aportó una nueva visión de la historia temprana de la complejidad computacional antes de su histórico artículo con Stearns, abordando las interacciones entre Turing , Gödel y Church. , Post y Kleene . Gödel, en esta carta, fue el primero en cuestionar si un problema equivalente a un problema NP-completo podría resolverse en tiempo cuadrático o lineal, presagiando el P = NP? pregunta .

Premios

Publicaciones Seleccionadas

Libros
Artículos seleccionados

Entrevistas

Juris Hartmanis ha sido entrevistado cuatro veces. Hay vídeos disponibles para dos de ellos. El de mayor alcance es el de William Aspray.

Referencias

  1. ^ "Juris Hartmanis". mathgenealogy.org . Proyecto Genealogía Matemática . Consultado el 4 de agosto de 2022 .
  2. ^ Selman, Alan L. , ed. (1990). Retrospectiva de la teoría de la complejidad: en honor a Juris Hartmanis con motivo de su sexagésimo cumpleaños, 5 de julio de 1988. Nueva York, NY: Springer New York. doi :10.1007/978-1-4612-4478-3. ISBN 978-1-4612-4478-3. S2CID  31789744 . Consultado el 4 de agosto de 2022 .
  3. ^ En las lenguas bálticas, los nombres propios no son constantes léxicas, sino que tienen diferentes formas gramaticales. Hartmanis debe entenderse como Hartman-is, donde Hartman es la raíz del nombre propio, mientras que el sufijo -is indica una forma gramatical masculina en el idioma letón. De manera similar, por ejemplo, el filósofo Kant es conocido como Kant en lengua lituana.
  4. ^ ab Hartmanis, Juris (26 de julio de 2009). "Entrevista al Dr. Juris Hartmanis" (texto). Entrevistado por William Aspray. Ithaca, Nueva York: Entrevistas de Historia Oral de ACM. doi : 10.1145/1141880.1775727 .
  5. ^ ab Hartmanis, Juris (17 de mayo de 2018). "Juris Hartmanis, ganador del premio ACM Turing 1993" (vídeo). Entrevistado por David Gries . Ithaca, Nueva York: ACM .
  6. ^ En dos de las entrevistas [4] [5] citadas en la sección #Entrevistas, Hartmanis habla en detalle de este período de su vida, en el que su padre recibió una propiedad, Lestene; los rusos ocuparon Letonia, se llevaron a su padre y confiscaron Lestene; los alemanes tomaron el poder una vez más y devolvieron parte de Lestene a su familia; y la familia abandonó Letonia hacia Alemania antes de que los rusos invadieran Letonia nuevamente.
  7. ^ "Un tributo a Astrid Ivask: una luz literaria". Literatura mundial hoy . 2 de abril de 2015 . Consultado el 4 de agosto de 2022 .
  8. ^ Hartmanis, Juris (1955). Algunos teoremas de incrustación para celosías (tesis doctoral). Cal Tech . doi :10.7907/40KS-0T27.
  9. ^ ab "Títulos honoríficos de la Universidad de Missouri". Universidad de Misuri .
  10. ^ab— ; Stearns, RE (11 de noviembre de 1964). Complejidad computacional de secuencias recursivas. 5to Ana. Síntoma. sobre teoría de circuitos de conmutación y diseño lógico. Princeton, Nueva Jersey: IEEE. págs. 82–90. doi :10.1109/SWCT.1964.6.
  11. ^ab— ; Lewis, PM; Stearns, RE (24 de mayo de 1963). Wayne A. Kalenich (ed.). Clasificaciones de cálculos por tiempo y requisitos de memoria . Proc. Congreso IFIP 65. Ciudad de Nueva York: Spartan Books, Inc., Washington, DC, págs. doi :10.2307/2272795. JSTOR  2272795.
  12. ^ abc— ; Lewis, PM; Stearns, RE (6 de octubre de 1965). "Jerarquías de cálculos con memoria limitada" . FOCS 65: Procesamiento. Sexta Ana. Teoría de circuitos de conmutación Symp y diseño lógico. Nueva York: IEEE . págs. 179-190. doi :10.1109/FOCS.1965.11.
  13. ^ abc— ; Stearns, RE (1965). "Sobre la complejidad computacional de los algoritmos". Transacciones de la Sociedad Matemática Estadounidense . 117 : 285–306. doi : 10.2307/1994208 . JSTOR  1994208. SEÑOR  0170805.
  14. ^ abc - (1981), "Observaciones sobre el desarrollo de la informática teórica", IEEE Annals of the History of Computing , 3 (1): 42–51, doi :10.1109/MAHC.1981.10005, hdl : 1813/6244 , ISSN  1058-6180
  15. ^ Estos primeros artículos desarrollaron muchos principios de la teoría de la complejidad computacional. [10] [11] [12] [13] El artículo de estudio de Hartmanis de 1981 proporciona amplia información sobre el trabajo en la teoría de la complejidad computacional. [14]
  16. ^ La Universidad Purdue creó el primer Departamento de informática en 1962 "Historia del Departamento".Cornell inició su Departamento de informática en 1965, "Cronología del departamento de informática".al igual que Stanford, "Cronología del Departamento de CS"., Carnegie Mellon, "Historia del Departamento de CS".y algunos otros.
  17. ^ Hartmanis, Juris; Lin, Herbert, eds. (1992). Computar el futuro: una agenda más amplia para la informática y la ingeniería . Washington, DC: Prensa de Academias Nacionales . pag. 288. doi : 10.17226/1982. ISBN 978-0-309-04740-1.
  18. ^ "Juris Hartmanis dirigirá la dirección de NSF para CISE". NSF . 5 de septiembre de 1996 . Consultado el 2 de agosto de 2022 .
  19. ^ ab Lista de miembros de la Sociedad Estadounidense de Matemáticas, consultado el 19 de enero de 2013.
  20. ↑ Electos miembros de la Academia Nacional de Ciencias y asociados extranjeros Archivado el 27 de mayo de 2013 en Wayback Machine , Academia Nacional de Ciencias , 30 de abril de 2013.
  21. ^ ab "Miembros extranjeros". Academia de Ciencias de Letonia . 1990 . Consultado el 30 de julio de 2022 .
  22. ^ ab "Lielā medaļa" [Gran Medalla]. www.lza.lv (en letón). Academia de Ciencias de Letonia . Archivado desde el original el 6 de enero de 2022 . Consultado el 4 de agosto de 2022 . 2001 ... Juris Hartmanis, par izcilu ieguldījumu datorzinātņu attīstībā. [2001... Juris Hartmanis, por su destacada contribución al desarrollo de la informática.]
  23. ^ 新智元 [Xin Zhi Yuan] (31 de julio de 2022). "图灵奖得主，"计算复杂性"理论奠基人Juris Hartmanis逝世，享年94岁" [Juris Hartmanis, ganador del Premio Turing y fundador de la teoría de la "complejidad computacional", muere a los 94 años].新浪 Finance.sina.com. cn (en chino simplificado) . Consultado el 4 de agosto de 2022 .
  24. ^ Waldron, Patricia (4 de agosto de 2022). "Juris Hartmanis, primer jefe del departamento de informática, muere a los 94 años". Crónica de Cornell . Consultado el 5 de agosto de 2022 .
  25. ^ Garfinkel, Simson; Spafford, Eugene H. (octubre de 2022). "In memoriam: Juris Hartmanis 1928-2022". MCCA . 65 (10): 14-15. doi : 10.1145/3559705 .
  26. ^ ab "Premio Turing". ACM . 1993 . Consultado el 30 de julio de 2022 .
  27. ^ Consulte la página 103 de su conferencia: Karp, Richard M. (febrero de 1986). "Combinatoria, complejidad y aleatoriedad". Comunicaciones de la ACM . 29 (2): 98-109. doi : 10.1145/5657.5658 . ISSN  0001-0782.
  28. ^ ab Lewis, PM; Stearns, RE ; - (6 de octubre de 1965). Límites de la memoria para el reconocimiento de lenguajes sensibles al contexto y libres de contexto. FOCS 65: Procesamiento. Sexta Ana. Teoría de circuitos de conmutación Symp y diseño lógico. Ann Arbor, Michigan: IEEE. págs. 191-202. doi :10.1109/FOCS.1965.14.
  29. ^ ab Berman, L.; — (1977). «Sobre isomorfismos y densidad de NP y otros conjuntos completos» (PDF) . Revista SIAM de Computación . 6 (2): 305–322. doi :10.1137/0206023. hdl : 1813/7101 . SEÑOR  0455536.
  30. ^ Conjetura de Berman-Hartmanis
  31. ^ Mahaney, Stephen R. (octubre de 1982). "Conjuntos completos dispersos para NP: Solución de una conjetura de Berman y Hartmanis". Revista de Ciencias de la Computación y de Sistemas . 25 (2): 130-143. doi :10.1016/0022-0000(82)90002-2. hdl : 1813/6257 .
  32. ^ Cai, Jin-Yi; Sivakumar, D. (abril de 1999), "Conjuntos duros dispersos para P: resolución de una conjetura de Hartmanis", Journal of Computer and System Sciences , 58 (2): 280–296, doi : 10.1006/jcss.1998.1615
  33. ^ Lenguaje escaso
  34. ^ Teorema de Mahaney
  35. ^ Cai, Jin-Yi; Gundermann, Thomas; —; Hemachandra, carril A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd (diciembre de 1988), "La jerarquía booleana I: propiedades estructurales", SIAM Journal on Computing , 17 (6): 1232–1252, doi : 10.1137/0217078
  36. ^ Cai, Jin-Yi; Gundermann, Thomas; —; Hemachandra, carril A.; Sewelson, Vivian; Wagner, Klaus; Wechsung, Gerd (febrero de 1989), "La jerarquía booleana II: Aplicaciones", Revista SIAM de Computación , 18 (1): 95–111, doi :10.1137/0218007
  37. ^ Selman, Alan L. , ed. (1990). Retrospectiva de la teoría de la complejidad . Springer Nueva York, Nueva York. doi :10.1007/978-1-4612-4478-3. ISBN 978-1-4612-8793-3. S2CID  31789744.
  38. ^ Stearns, RE (1990). "Juris Hartmanis: Los inicios de la complejidad computacional". En Selman, Alan L. (ed.). Retrospectiva de la teoría de la complejidad . Springer Nueva York, Nueva York. doi :10.1007/978-1-4612-4478-3. ISBN 978-1-4612-8793-3. S2CID  31789744.
  39. ^ ab Hartmanis, Juris (1989). "Gödel, von Neumann y el problema P =? NP". Boletín de la Asociación Europea de Informática Teórica . 38 : 101-107.
  40. ^ "Becarios". Asociación Estadounidense para el Avance de la Ciencia . 1981 . Consultado el 30 de julio de 2022 .
  41. ^ "Sitio web de la NAE: Dr. Juris Hartmanis". Academia Nacional de Ingeniería .
  42. ^ "Miembros". Academia Estadounidense de Artes y Ciencias . 1992 . Consultado el 30 de julio de 2022 .
  43. ^ "Fundación Alexander von Humboldt, Juris Hartmanis". Fundación Alejandro von Humboldt . 1993.
  44. ^ "Becarios ACM". ACM . 1994 . Consultado el 30 de julio de 2022 .
  45. ^ "Juris Hartmanis: miembro de ACM". 1994 . Consultado el 9 de julio de 2022 .
  46. ^ "Premio al Servicio Distinguido". Asociación de Investigación en Computación . CRA . 16 de enero de 2015 . Consultado el 30 de julio de 2022 .
  47. ^ "Premio al Servicio Distinguido ACM". ACM . 2013 . Consultado el 30 de julio de 2022 .
  48. ^ "Juris Hartmanis: Premio al Servicio Distinguido". 2013 . Consultado el 30 de julio de 2022 .
  49. ^ "Miembro Emérito". Academia Nacional de Ciencias (NAS) . Consultado el 31 de julio de 2022 .
  50. ^ —; Richard E., Stearns (1966). Teoría de la estructura algebraica de máquinas secuenciales . Englewood Cliffs, Nueva Jersey: Prentice-Hall. pag. 211.ISBN​ 0130222771.
  51. ^ - (1978). Cálculos factibles y propiedades de complejidad demostrables . Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas (SIAM) . pag. 62.ISBN​ 978-0-898710-27-4.
  52. ^ —, ed. (1989). Teoría de la complejidad computacional. AMS . pag. 128.ISBN​ 978-0-8218-0131-4.
  53. ^ —; Lin, Herbert, eds. (1992). Computar el futuro: una agenda más amplia para la informática y la ingeniería . Washington, DC: Prensa de las Academias Nacionales . pag. 288. doi : 10.17226/1982. ISBN 978-0-309-04740-1.
  54. ^ Hartmanis, Juris (31 de marzo de 2010). "Una conversación con Juris Hartmanis" (vídeo). Entrevistado por David Gries . Ithaca, Nueva York: Internet-First University Press.
  55. ^ Shustek, Len (2015). "Una entrevista con Juris Hartmanis". MCCA . 58 (4): 33–37. doi :10.1145/2736346. S2CID  35051248.

enlaces externos