La conjectura de Hirsch refutada per Francisco Santos (Universidad de Catabria)

La conjectura de Hirsch posava un límit als resultats de l'algorisme simplex (optimització, programació matemàtica) per tractar problemes pesants, però el matemàtic Francisco Santos (Universidad de Cantabria) l'ha pogut refutar; això dóna volada als esforços de computació per resoldre problemes difícils fent servir l'algorisme simplex. El següent article tracta el tema amb profunditat: http://www.madrimasd.org/blogs/matematicas/2010/05/23/131798

El problema de Basilea (L. Euler) i la funció zeta de Riemann

El següent article [http://ca.wikipedia.org/wiki/Problema_de_Basilea] és força interessant pel que fa a la suma de sèries infinites, concretament la de l'invers de i2 (1=1,2,3,....) que, tal com va demostrar L. Euler està relacionada amb el nombre pi. A, més, la generalització de l'exponent defineix la funció zeta de Riemann, quelcom molt important en teoria de nombres pel fet d'estar lligada amb els nombres primers.

Els set problemes del mil·leni

El Clay Mathematics Institute va proposar l'any 2000. Per la resolució de cadascun d'aquests 7 problemes (Wikipedia), l'institució va dotar un premi corresponent d'un milió de dòlars. Entre aquests problemes apareix també el problema conegut amb el nom d'hipòtesi de Riemann, que ja constava a la llista de 23 problemes que David Hilbert va proposar l'any 1900 en el famós Congrès Internacional de Matemàtics que es cel·lebrà aquell any a Paris, un any abans que el segle XIX i la seva panoràmica científica donés pas al nou segle XX, en aquell moment, amb un panorama crític i a la vegada ric en idees i nous problemes en molts camps del coneixement científic fonamental, especialment en el camp de la Física i la Matemàtica. Els problemes de Hilbert van ser - i són encara, molts d'ells - problemes de referència emblemàtica; alguns han estat resolts (el gran teorema de Fermat (demostrat el 1994) i la conjectura de Poincaré (fa molt poc), per exemple; altres, encara no (la conjectura de Goldbach, n'és un de molt famós, de la qual ja n'he parlat en d'altres escrits). Un dels set problemes que figuren a la llista dels Problemes del Mil·leni, amb la qual els matemàtics que estan al capdavant de la recerca fonamental miren de perfilar un futur panorama matemàtic per al segle XXI alhora que proposar motivacions, i reptes de progrès continu en la investigació matemàtica pura i aplicada, ja ha estat resolt: la conjectura de Poincaré. Com molts dels problemes de la llista de Hilbert, els set problemes del Clay van més enllà de la matemàtica, incideixen de ple en els problemes de la física: desenvolupar la mecànica quàntica per poder entendre l'univers físic i agermanar els diversos nivells d'observació, entendre la dinàmica no lineal, copsar la impredictibilitat fonamental de la naturalesa, matematitzar la complexitat ... Entre els problemes d'una llista, la de Hilbert, i l'altra, la del Clay, no es pot pas dir que falten reptes de primer ordre. Per llegir més sobre els problemes, a més a més del vincle de la Wikipedia que he resenyat a dalt, també podreu trobar informació en aquest altre lloc [ http://personales.ya.com/casanchi/mat/milenio00.htm ] informació sobre la naturalesa i estat de la qüestió d'aquests problemes. Aquests són els 7 problemes: Problema P versus NP[computabilitat, complexitat algorísmica] La conjectura de Hodge [àlgebra, espais projectius] La no linealitat de les equacions de Navier-Stokes [dinàmica de fluïds, dinàmica no lineal] La conjectura de Poincaré [topologia] (problema resolt) La hipòtesis de Riemann [nombres primers, teoria de nombres] La teoria de Yang-Mills [mecànica quàntica, topologia] La Conjetura de Birch i Swinnerton-Dyer [teoria de nombres, equacions diofàntiques (equacions amb nombres enters)]

P=NP ?

He llegit l'article que escriu Agustín Royo a la secció “juegos matemáticos” de la revista Investigación y Ciencia del mes d'abril de 2010. Aquesta vegada exposa un dels problemes del mil·leni proposats per l'institut de recerca matemàtica Clay (Cambridge, Massachusetts): el problema al qual hom se sol refererir amb la grafia P = NP, que, com és comprensible, serà impossible, a primer cop d'ull, extraure'n algun significat si el lector no està al corrent dels problemes sobre computació. Agustín Royo, però, aconsegueix explicar-ho amb una gran claredat a qualsevol lector amb un mínim d'interès i un coneixement matemàtic elemental. En faré tot seguit un resum perquè trobo molt interessant donar-li la màxima difusió a problemes matemàtics de tanta profunditat com aquest. Vegem què vol dir això de P = NP. Comença l'autor a parlar del problema de computació conegut com el problema de la suma de subconjunts. Es tracta d'escollir un conjunt de nombres enters i, a partir dels seus elements, cal decidir si algun dels seus subconjunts no buits és tal que la suma dels elements que el formen és igual a zero. Donat un conjunt de n elements, el nombre de subconjunts no buits que es poden formar a partir d'aquest conjunt és igual a 2n -1. Un algorisme simple que examinés tots els possibles subconjunts podria haver de fer més de 2n operacions per donar una resposta a la pregunta. La dependència entre el nombre d'elements i el nombre d'operacions a realitzar – quantitat que dóna el temps de computació – és en aquest cas exponencial. Seria possible trobar un algorisme eficient que pogués decidir el problema exposat en dependència polinomial (nombre d'operacions necessàries de l'ordre de nk << 2 n, on l'exponent de la potència, k, és constant)? De fet, encara es desconeix la resposta a aquesta pregunta. Els problemes de computació que es poden resoldre (decidir) mitjançant algun algorisme amb dependència potencial constitueixen el conjunt de problemes anomenat P. Si tots els problemes estiguessin en P – si tots els problemes es poguessin resoldre mitjançant algun algorisme eficient (en temps polinomial) – seria molt poc costós, per exemple, trencar claus criptogràfiques, o fer simulacions complexes de qualsevol sistema; malauradament, com és ben evident, això no és pas així. Ara bé, hi ha un tercer conjunt de problemes de computació que anomenem NP. Per quins problemes està format ? Suposem que algú proposa una solució al problema de la suma de subconjunts (almenys un subconjunt la suma dels elements del qual és igual zero). Per bé que, de moment, no se sap si el problema de la suma de subconjunts es pot decidir en P (en temps polinomial), sí que és fàcil, no obstant, escriure un algorisme per verificar la solució proposada; un algorisme, a més, amb dependència polinomial entre el nombre d'elements a verificar i el nombre d'operacions a realitzar. El conjunt de problemes amb solució proposada i verificable en temps polinomial com ara el problema de la suma de subconjunts s'anomena NP. El que fa tan interessant el problema de la suma de subconjunts és el fet que es pot demostrar que qualsevol problema en NP es pot reduir al problema de la suma de subconjunts. D'aquí sorgeix un interessant repte matemàtic: si es pogués trobar un algorisme eficient (temps polinomial) per resoldre el problema de la suma de subconjunts, quedaria demostrat que tot problema en NP és, de fet, un problema en P (NP = P). Referències: ROYO, A.   P=NP. Problema del milenio, (Juegos Matemáticos), Investigación y Ciencia, abril de 2010.

Informació Quàntica

El tractament quàntic de la informació (q-bits) es fonamenta en el paradigma quàntic i s'obre en diversos fronts: computació quàntica, criptografia quàntica, comunicació, i dispositius físics (q-portes lògiques) [basats en sistemes atòmics, iònics, fotònics, d'estat sòlid, o bé barreges d'aquests] que permetin implementar de forma real els algorismes dissenyats per al càlcul paral·lel (q-algorismes/programes). No cal dir que la base d'aquestes aplicacions és la teoria de la mecànica quàntica. Un problema de computació tractat amb algorismes adaptats a la computació quàntica (q-algorismes) guanya en rapidesa en relació als corresponents algorismes clàssics. Un dels algorismes quàntics més estudiats és l'algorisme de Shor (Peter Shor). L'algorisme de Shor serveix per expressar un nombre enter com a producte de nombres primers. Hi ha molts algorismes clàssics que fan el mateix, és clar, però el de Shor dóna el resultant en temps polinòmic, en concret, de tal manera que si el nombre a factoritzar és n, la tasca s'efectua en un temps O((log n)3). Els algorismes clàssics no permeten fer aquesta tasca de forma tan ràpida: per a n donat, si aquest és un nombre considerablement gran, no la poden dur a terme en temps O((log n)k) sigui quin sigui k. Val a dir que els mètodes d'encriptació RSA es basen en la dificultat que comporta intentar trencar la clau si aquesta està formada per un nombre enter molt gran. La possible implementació d'algorismes quàntics de forma pràctica sí que ho podria fer. És per això que el futor paradigma criptogràfic sembla que s'allunyi del de la criptografia de clau pública (RSA) ja que aquesta via ja no garantiria la seguretat. Referències: Seguint el següent vincle es pot consultar material d'introducció: [https://en.wikipedia.org/wiki/Quantum_information]