{"id":465404,"date":"2016-01-19T09:40:04","date_gmt":"2016-01-19T14:40:04","guid":{"rendered":"http:\/\/diarioelpopular.com\/?p=465404"},"modified":"2016-01-19T09:40:12","modified_gmt":"2016-01-19T14:40:12","slug":"premio-fundacion-bbva-fronteras-del-conocimiento-a-stephen-cook-por-determinar-que-hay-problemas-que-los-ordenadores-no-pueden-resolver-de-forma-eficiente","status":"publish","type":"post","link":"https:\/\/diarioelpopular.com\/index.php\/2016\/01\/19\/premio-fundacion-bbva-fronteras-del-conocimiento-a-stephen-cook-por-determinar-que-hay-problemas-que-los-ordenadores-no-pueden-resolver-de-forma-eficiente\/","title":{"rendered":"Premio Fundaci\u00f3n BBVA Fronteras del Conocimiento a Stephen Cook por determinar que hay problemas que los ordenadores no pueden resolver de forma eficiente"},"content":{"rendered":"<ul>\n<li>Al concepto de computabilidad de Turing \u2013qu\u00e9 puede resolver o no un ordenador- Cook incorpora la eficiencia, permitiendo prever cu\u00e1ndo merece la pena esforzarse por resolver un problema o solo ser\u00e1 viable una aproximaci\u00f3n<\/li>\n<li>Cook define una clase de problemas, los NP-completos, que son los de m\u00e1xima dificultad y que est\u00e1n vinculados, de modo que si se hallara la soluci\u00f3n eficiente a uno de ellos querr\u00eda decir que todos los dem\u00e1s tambi\u00e9n la tendr\u00edan<\/li>\n<li>Cook plantea uno de los grandes Problemas del Milenio y es si llegar\u00e1 a haber soluci\u00f3n eficiente para los NP-completos, lo que, adem\u00e1s, comprometer\u00eda los actuales sistemas de encriptado y la seguridad que son la base de la econom\u00eda digital<\/li>\n<\/ul>\n<p><strong>Madrid, 12 de enero de 2016.-<\/strong>El matem\u00e1tico Stephen Arthur Cook ha sido galardonado con el premio Fundaci\u00f3n BBVA Fronteras del Conocimiento en la categor\u00eda de Tecnolog\u00edas de la Informaci\u00f3n y la Comunicaci\u00f3n \u201cpor su importante papel a la hora de determinar qu\u00e9 pueden los ordenadores resolver de forma eficiente y qu\u00e9 no\u201d, se\u00f1ala el acta del jurado. Su trabajo \u201cha tenido un impacto decisivo en todos aquellos campos en los que los c\u00e1lculos complejos son de vital importancia\u201d.<\/p>\n<p>Saber si un problema es soluble o no en un tiempo asumible es esencial para decidir c\u00f3mo enfrentarse a \u00e9l. Stephen Cook descubri\u00f3 una clase espec\u00edfica de problemas, llamada <em>NP-completos<\/em>, tal que -como \u00e9l mismo explic\u00f3 ayer por tel\u00e9fono tras recibir la noticia del premio- \u201csi puedes demostrar que un problema es NP-completo, entonces lo que deber\u00edas hacer es simplemente dejar de intentar resolverlo\u201d.<\/p>\n<p>Esta sabidur\u00eda a la hora de decidir cu\u00e1ndo rendirse parecer\u00eda una derrota, pero desde el punto de vista de las aplicaciones pr\u00e1cticas resulta ser todo lo contrario: en vez de desperdiciar esfuerzos persiguiendo un imposible, los programadores ensayan estrategias \u201cmucho m\u00e1s \u00fatiles -dice Cook- por ejemplo buscar soluciones aproximadas\u201d.<\/p>\n<p>Cook es catedr\u00e1tico de Ciencias de la Computaci\u00f3n en la Universidad de Toronto. Su nominaci\u00f3n defiende que su aportaci\u00f3n es, junto al concepto de \u201ccomputabilidad\u201d de Alan Turing, uno de los hitos en la fundamentaci\u00f3n matem\u00e1tica de la computaci\u00f3n. Si Turing defini\u00f3 qu\u00e9 pueden resolver los ordenadores y qu\u00e9 no, Cook incorpor\u00f3 el principio de eficiencia para determinar qu\u00e9 pueden resolver de forma eficiente y qu\u00e9 no.<\/p>\n<p>\u201cHay problemas que en principio pueden ser resueltos por un ordenador, pero la m\u00e1quina tardar\u00eda tanto que el sol morir\u00eda antes -prosigue Cook-. Esos son los problemas que llamamos NP. Y est\u00e1n los problemas que llamamos P, que s\u00ed pueden ser resueltos en un tiempo razonable. La cuesti\u00f3n es decidir qu\u00e9 problemas son NP [no solubles eficientemente], y cu\u00e1les son P [f\u00e1cilmente solubles]\u201d.<\/p>\n<p>La principal aportaci\u00f3n de Cook fue determinar que dentro de la clase NP, hab\u00eda una subclase que denomin\u00f3 NP completa, y cuyo rasgos distintivos son que, adem\u00e1s de ser los m\u00e1s dif\u00edciles, son computacionalmente equivalentes; es decir, si se hallara un algoritmo eficiente para uno de ellos, significar\u00eda que existe un algoritmo para el resto y no solo de los NP completos, sino para el conjunto de los NP.<\/p>\n<p>Como afirma el acta del jurado, \u201cel concepto de \u201cNP-completo\u201d se considera uno de los principios fundamentales de la ciencia de la computaci\u00f3n\u201d. Hoy se conocen literalmente miles de problemas NP completos en \u00e1mbitos muy diversos: biolog\u00eda, f\u00edsica, econom\u00eda, teor\u00eda de n\u00fameros, l\u00f3gica, optimizaci\u00f3n\u2026 Un ejemplo es la forma en que las prote\u00ednas adquieren su estructura tridimensional, un problema esencial en biolog\u00eda; otro es el famoso problema del viajante: hallar la ruta m\u00e1s eficiente que debe seguir un repartidor para llegar a muchos destinatarios.<\/p>\n<p>La definici\u00f3n de los problemas NP-completos proporciona importantes directrices para los cient\u00edficos e ingenieros, y tambi\u00e9n para los t\u00e9cnicos inform\u00e1ticos, que deben dise\u00f1ar los algoritmos con que hacer frente a los problemas.<\/p>\n<p>Cook public\u00f3 su <em>paper<\/em> m\u00e1s influyente en 1971, poco despu\u00e9s de doctorarse. Parti\u00f3 de un determinado problema NP, y entonces no imaginaba cu\u00e1ntos problemas de ese tipo exist\u00edan. Sab\u00eda que el concepto con el que trabajaba era \u201cinteresante\u201d \u2013dijo ayer-, pero no sospechaba que acabar\u00eda siendo tan importante. Solo un a\u00f1o despu\u00e9s de la publicaci\u00f3n de su trabajo otro matem\u00e1tico public\u00f3 una lista con unos trescientos problemas NP, es decir, problemas que los ordenadores no pueden resolver de forma eficiente.<\/p>\n<p><strong>Problema del Milenio<\/strong><\/p>\n<p>El trabajo de Cook dio lugar tambi\u00e9n al que hoy es considerado uno de los principales problemas sin resolver de las matem\u00e1ticas: el problema de &#8220;P versus NP&#8221;. Es uno de los siete problemas incluidos en la lista de \u2018Problemas del Milenio\u2019 del Clay Mathematics Institute (EE.UU.), cuya resoluci\u00f3n se premia con un mill\u00f3n de d\u00f3lares.<\/p>\n<p>En t\u00e9rminos no t\u00e9cnicos, el problema &#8220;P versus NP\u201d se pregunta si de verdad no existe ninguna otra manera m\u00e1s r\u00e1pida, ning\u00fan atajo brillante, que permita resolver los problemas NP. Por ejemplo, en el problema del repartidor, hoy por hoy la \u00fanica manera de hallar la ruta m\u00e1s r\u00e1pida es calcular todas las trayectorias posibles; es un problema NP porque cuando los destinatarios son muchos hay que hacer tantos c\u00e1lculos que en la pr\u00e1ctica el problema es irresoluble. Pero \u00bfseguro que no existe un algoritmo que d\u00e9 una soluci\u00f3n sin necesidad de hacer todos esos c\u00e1lculos? Eso es lo que plantea el problema &#8220;P versus NP\u201d.<\/p>\n<p>Hoy la inmensa mayor\u00eda de los matem\u00e1ticos cree que no hay un algoritmo as\u00ed, y que por tanto los problemas NP <em>realmente<\/em> son irresolubles. Es decir, P y NP son problemas de verdad distintos en complejidad. Pero nadie lo ha demostrado, y \u201cno creo que nadie lo vaya a hacer a corto plazo\u201d, dijo ayer Cook.<\/p>\n<p>La clase de problemas que \u00e9l descubri\u00f3, los<strong> NP-completos<\/strong>, son en cierto modo problemas \u2018llave\u2019, porque son un tipo espec\u00edfico de problemas NP que, si se demuestra que existe un algoritmo que los resuelva, \u201centonces todos los problemas NP podr\u00edan resolverse f\u00e1cilmente\u201d, explica Cook, \u201cy eso implica que las dos clases P y NP coincidir\u00edan\u201d. Bastar\u00eda con resolver un \u00fanico problema NP completo para demostrar que ning\u00fan NP es irresoluble. Pero Cook insiste: \u201cNosotros creemos que P y NP son distintos, y que NP son realmente dif\u00edciles\u201d.<\/p>\n<p>Como explica el acta, 45 a\u00f1os de esfuerzos combinados de inform\u00e1ticos y matem\u00e1ticos no han servido para hallar un algoritmo eficiente para los problemas NP-completos.<\/p>\n<p>Si se encontrara ese algoritmo, las implicaciones ser\u00edan enormes, porque comprometer\u00eda el sistema de encriptado \u2013fundamentado en problemas NP- y la seguridad que son la base de la econom\u00eda digital.<\/p>\n<p>Cook se mostr\u00f3 ayer \u201cmuy sorprendido\u201d y \u201cencantado\u201d con el premio. A lo largo de su carrera ha sido testigo de \u201cc\u00f3mo las ciencias de la computaci\u00f3n evolucionaban de forma impresionante\u201d, algo que le fascina.<\/p>\n<p><strong>Biograf\u00eda<\/strong><\/p>\n<p>Stephen Arthur Cook (Buffalo, Nueva York, Estados Unidos, 1939) ostenta la doble nacionalidad estadounidense y canadiense. Hijo de un qu\u00edmico y un ama de casa con dos m\u00e1ster (en Ingl\u00e9s y en Historia), su primera vocaci\u00f3n fue la ciencia aplicada. De hecho, mientras cursaba secundaria ayud\u00f3 a Wilson Greatbatch, el inventor del primer marcapasos cardiaco implantable, a soldar circuitos en los primeros prototipos del dispositivo.<\/p>\n<p>Cuando se matricul\u00f3 en la Universidad de Michigan -donde sus padres se hab\u00edan conocido- opt\u00f3 por Ciencias de la Ingenier\u00eda, pero destac\u00f3 tanto en las asignaturas de Matem\u00e1ticas que acab\u00f3 dando el salto a esta carrera y obtuvo la licenciatura en 1961.<\/p>\n<p>Tras hacer los estudios de m\u00e1ster fue a Harvard a hacer el doctorado. En aquel momento no estaba especialmente interesado en la computaci\u00f3n. Como \u00e9l mismo afirma: \u201cNi siquiera sab\u00eda realmente lo que quer\u00eda hacer; puse \u00c1lgebra como mi \u00e1rea\u201d. Pero all\u00ed descubri\u00f3, entre otros, los <em>papers<\/em> de Alan Cobham sobre complejidad computacional y acab\u00f3 haciendo la tesis doctoral en este campo, en concreto sobre la complejidad de la multiplicaci\u00f3n.<\/p>\n<p>A continuaci\u00f3n se incorpor\u00f3 al Departamento de Matem\u00e1ticas de la Universidad de Berkeley, donde estuvo cuatro a\u00f1os. De ah\u00ed march\u00f3, en 1970, al Departamento de Ciencia de la Computaci\u00f3n de la Universidad de Toronto, donde contin\u00faa siendo catedr\u00e1tico. Un a\u00f1o m\u00e1s tarde hizo su aportaci\u00f3n seminal en el paper <em>\u201cThe complexity of Theorem Proving Procedures\u201d<\/em>, que present\u00f3 en el congreso del Special Interest Group on Algorithms and Computational Theory de la Association for Computing Machinery.<\/p>\n<p><strong>Sobre los Premios Fundaci\u00f3n BBVA Fronteras del Conocimiento<\/strong><\/p>\n<p>En 2008 la Fundaci\u00f3n BBVA cre\u00f3 los premios Fronteras del Conocimiento para reconocer a los autores de avances particularmente significativos en un amplio abanico de \u00e1reas cient\u00edficas, tecnol\u00f3gicas y art\u00edsticas, disciplinas que responden al mapa del conocimiento en la \u00faltima parte del siglo XX y en el presente, as\u00ed como a retos fundamentales como el cambio clim\u00e1tico y la cooperaci\u00f3n al desarrollo, \u00e1reas todas ellas merecedoras de una mayor visibilidad y reconocimiento social.<\/p>\n<p>Las <strong>ocho categor\u00edas<\/strong> incluyen \u00e1reas cl\u00e1sicas &#8211;<em>Ciencias <\/em>y <em>Biomedicina-; <\/em>otras m\u00e1s recientes, caracter\u00edsticas de nuestro tiempo &#8211;<em>Tecnolog\u00edas de la Informaci\u00f3n y la Comunicaci\u00f3n, Ecolog\u00eda y Biolog\u00eda de la Conservaci\u00f3n, Cambio Clim\u00e1tico, Econom\u00eda, Finanzas y Gesti\u00f3n de Empresas, y Cooperaci\u00f3n al Desarrollo;<\/em> y un \u00e1rea particularmente innovadora de las artes, <em>M\u00fasica Contempor\u00e1nea<\/em>.<\/p>\n<p>Los <strong>jurados<\/strong> de cada categor\u00eda est\u00e1n compuestos por destacados expertos en sus respectivas \u00e1reas. En la organizaci\u00f3n de los premios la Fundaci\u00f3n BBVA cuenta con la colaboraci\u00f3n del <strong>Consejo Superior de Investigaciones Cient\u00edficas (CSIC), <\/strong>que designa comisiones t\u00e9cnicas de evaluaci\u00f3n que llevan a cabo una primera valoraci\u00f3n de las candidaturas y, posteriormente, elevan al jurado una propuesta razonada de finalistas.<\/p>\n<p>En la categor\u00eda de TIC los miembros de la <strong>comisi\u00f3n t\u00e9cnica del CSIC<\/strong> han sido <strong>Juan Jos\u00e9 Garc\u00eda Ripoll<\/strong>, cient\u00edfico titular en el Instituto de F\u00edsica Fundamental del Consejo Superior de Investigaciones Cient\u00edficas (IFF-CSIC); <strong>Manuel Lozano Fantoba<\/strong>; profesor de investigaci\u00f3n y coordinador del \u00e1rea de Ciencia y Tecnolog\u00edas F\u00edsicas en el Instituto de Microelectr\u00f3nica de Barcelona. Centro Nacional de Microelect\u00f3nica, del Consejo Superior de Investigaciones Cient\u00edficas (IMB-CNM-CSIC); <strong>Pedro Meseguer Gonz\u00e1lez<\/strong>, investigador cient\u00edfico del Instituto de Investigaci\u00f3n en Inteligencia Artificial del Consejo Superior de Investigaciones Cient\u00edficas (IIIA-CSIC); <strong>Salvador Miret Artes<\/strong>, profesor de investigaci\u00f3n en el Instituto de F\u00edsica Fundamental del Consejo Superior de Investigaciones Cient\u00edficas de Madrid (IFT-CSIC) y <strong>Carmen Torras Genis<\/strong>, profesora de investigaci\u00f3n del Instituto de Rob\u00f3tica e Inform\u00e1tica Industrial del Consejo Superior de Investigaciones Cient\u00edficas (IRII &#8211; CSIC).<\/p>\n<p><strong>Jurado de Tecnolog\u00edas de la Informaci\u00f3n y la Comunicaci\u00f3n<\/strong><\/p>\n<p>El jurado de esta categor\u00eda est\u00e1 presidido por <strong>Georg Gottlob<\/strong>, catedr\u00e1tico de Ciencias de la Computaci\u00f3n de la Universidad de Oxford (Reino Unido), y cuenta como secretario con <strong>Ram\u00f3n L\u00f3pez de M\u00e1ntaras<\/strong>, director del Instituto de Investigaci\u00f3n en Inteligencia Artificial del Consejo Superior de Investigaciones Cient\u00edficas (CSIC). El resto de los miembros son <strong>Oussama Khatib<\/strong>, director del Laboratorio de Rob\u00f3tica y catedr\u00e1tico de Ciencias de la Computaci\u00f3n de la Universidad de Stanford (Estados Unidos);<strong> Rudolf Kruse, <\/strong>catedr\u00e1tico de la Facultad de Ciencias de la Computaci\u00f3n de la Universidad Otto-von-Guerike-Universit\u00e4t de Magdeburg (Alemania); <strong>Mateo Valero, <\/strong>director del Barcelona Supercomputing Center (Espa\u00f1a), y <strong>Joos Vandewalle, <\/strong>director de la SCD Divisi\u00f3n del Departamento de Ingenier\u00eda El\u00e9ctrica de la Universidad Cat\u00f3lica de Lovaina (B\u00e9lgica).<\/p>\n<p><strong>Premiados otras ediciones <\/strong><\/p>\n<p>Puede conocer los galardonados de otros a\u00f1os en el siguiente<a href=\"http:\/\/www.fbbva.es\/TLFU\/tlfu\/esp\/microsites\/premios\/fronteras\/galardonados\/2015\/index.jsp\"> link<\/a>:<\/p>\n<p><strong><a href=\"http:\/\/www.fbbva.es\/TLFU\/tlfu\/esp\/microsites\/premios\/fronteras\/galardonados\/2015\/index.jsp\">http:\/\/www.fbbva.es\/TLFU\/tlfu\/esp\/microsites\/premios\/fronteras\/galardonados\/2015\/index.jsp<\/a><\/strong><\/p>\n<p><strong>CALENDARIO DE ANUNCIO DE LOS PR\u00d3XIMOS GALARDONADOS<\/strong><\/p>\n<p>&nbsp;<\/p>\n<table width=\"454\">\n<tbody>\n<tr>\n<td width=\"284\"><strong>CATEGOR\u00cdA<\/strong><\/td>\n<td width=\"170\"><strong>FECHA<\/strong><\/td>\n<\/tr>\n<tr>\n<td width=\"284\"><strong>Ciencias B\u00e1sicas<\/strong><\/td>\n<td width=\"170\">Martes, 19 de enero de 2016<\/td>\n<\/tr>\n<tr>\n<td width=\"284\"><strong>Biomedicina<\/strong><\/td>\n<td width=\"170\">Martes, 26 de enero de 2016<\/td>\n<\/tr>\n<tr>\n<td width=\"284\"><strong>Ecolog\u00eda y Biolog\u00eda de la Conservaci\u00f3n<\/strong><\/td>\n<td width=\"170\">Martes, 2 de febrero de 2016<\/td>\n<\/tr>\n<tr>\n<td width=\"284\"><strong>M\u00fasica Contempor\u00e1nea<\/strong><\/td>\n<td width=\"170\">Martes, 9 de febrero de 2016<\/td>\n<\/tr>\n<tr>\n<td width=\"284\"><strong>Econom\u00eda, Finanzas y Gesti\u00f3n de Empresas<\/strong><\/td>\n<td width=\"170\">Martes, 16 de febrero de 2016<\/td>\n<\/tr>\n<tr>\n<td width=\"284\"><strong>Cooperaci\u00f3n al Desarrollo<\/strong><\/td>\n<td width=\"170\">Martes, 23 de febrero de 2016<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table>\n<tbody>\n<tr>\n<td width=\"361\">\n<p><strong>\u00a0<\/strong><\/p>\n<p><strong>PRIMERAS DECLARACIONES E IM\u00c1GENES DEL PREMIADO<\/strong><\/p>\n<p>Pueden acceder a un v\u00eddeo con la primera entrevista al premiado tras recibir la noticia del galard\u00f3n en el FTP de Atlas con estas coordenadas y nombre:<\/p>\n<p>Servidor:<strong>213.0.38.61<\/strong><\/p>\n<p>Usuario: <strong>AgenciaAtlas5<\/strong><\/p>\n<p>Contrase\u00f1a: <strong>premios<\/strong><\/p>\n<p>El v\u00eddeo lleva por nombre:<\/p>\n<p><strong>\u201cPREMIO TIC PROFESOR STEPHEN ARTHUR COOK\u201d<\/strong><\/p>\n<p>En caso de incidencias, por favor, contactad con Alejandro Mart\u00edn de la productora ATLAS:<\/p>\n<p><strong>M\u00f3vil: <\/strong>639 16 58 61<\/p>\n<p><strong>E-Mail:<\/strong> <a href=\"mailto:amartin@atlas-news.com\">amartin@atlas-news.com<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>Para m\u00e1s informaci\u00f3n, p\u00f3ngase en contacto con el Departamento de Comunicaci\u00f3n y Relaciones Institucionales de la Fundaci\u00f3n BBVA (91 374 52 10, 91 537 37 69, 91 374 81 73 o<a href=\"mailto:comunicacion@fbbva.es\">comunicacion@fbbva.es<\/a>) o consultar en la <em>web<\/em> <a href=\"http:\/\/www.fbbva.es\/\">www.fbbva.es<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la categor\u00eda de Tecnolog\u00edas de la Informaci\u00f3n y la Comunicaci\u00f3n<\/p>\n","protected":false},"author":5842,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24],"tags":[],"class_list":["post-465404","post","type-post","status-publish","format-standard","hentry","category-mundo"],"_links":{"self":[{"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/posts\/465404","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/users\/5842"}],"replies":[{"embeddable":true,"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/comments?post=465404"}],"version-history":[{"count":2,"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/posts\/465404\/revisions"}],"predecessor-version":[{"id":465406,"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/posts\/465404\/revisions\/465406"}],"wp:attachment":[{"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/media?parent=465404"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/categories?post=465404"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/diarioelpopular.com\/index.php\/wp-json\/wp\/v2\/tags?post=465404"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}