Anex:Problemes no resolts de les ciències de la computació

Els següents són alguns dels problemes no resolts de les ciències de la computació. Una solució dels problemes d'esta llista tindria un impacte notable en el camp d'estudi al que pertanyen.

Teoria de complexitat computacional (P versus NP)

Decidir si l'inclusió entre les classes de complexitat P i NP és estricta.

Font:

• S. A. Cook i Leonid Levin
• Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158.

Descripció: P és la classe de problemes la solució dels quals pot trobar-se en temps polinòmic. NP és la classe de problemes la solució dels quals pot trobar-se en temps polinòmic per una màquina de Turing no determinista (alternativament NP és la classe de problemes la solució dels quals pot verificar-se en temps polinòmic per una màquina de Turing determinista). Naturalment, qualsevol problema en P també es troba en NP. La qüestió P versus NP és si NP està en P i si les classes són iguals. Es pot vore esta qüestió com un cas específic del problema de provar llímits inferiors de costs per a problemes computacionals.

Importància: Si les classes són iguals llavors podem resoldre molts problemes que actualment considerem intractables. Si no, llavors els problemes NP-complets són provablement problemes que són NP-hard.

Conjectura actual: Encara que la pregunta està llunt de solucionar-se, sembla que les classes són distintes.

Criptografia

¿Existixen les funcions d'un sol sentit?

Font:

• W.Diffie, M.E.Hellman
• IEEE Trans. Inform. Theory, IT-22, 6, 1976, pp.644-654
• Còpia en llínea (HTML)

Descripció: Les funcions d'un sol sentit són fàcils de calcular pero difícils d'invertir. Algunes persones conjeturan que el logaritmo discret i l'inversió RSA són funcions d'un sol sentit.

Importància: Si les funcions d'un sol sentit existixen, llavors la criptografia de clau pública (public key cryptography) és possible. La seua existència implicaria que P no és NP.

Conjectura actual: Està assumit pero no provat que existixen.

Informàtica d'alt rendiment

¿Fins a quin grau es pot aumentar la velocitat de la computació?

Font:

Descripció: Encara que el teorema de l'aument de velocitat de la teoria de computació indica que qualsevol computació pot accelerar-se per una constant, no hi ha método de guanyar dita millora de velocitat. Es necessita saber quins són les tècniques i llímit en vàries arquitectura.

Importància: La velocitat de computació és el llímit als problemes que podem resoldre.

Conjectura actual: La Llei de Amdahl és una solució parcial al problema.

¿Cóm es pot construir un cluster de computadors de N nodos?

Font:

Descripció: Mentres que el número d'ordenadors en un cluster aumenta, la provabilitat de fallo en un d'estos també aumenta. En un punt, la mija de temps entre fallos és menor que els temps de recuperació i comprovació. ¿És possible d'alguna forma que l'aument de la provabilitat de fallo llimite la taxa d'increment de potència?

Importància: Els clusters són un método poderós de guanyar potència de computació. Aixina, les llimitacions del tamany del cluster també ho són de la potència de càlcul.

Conjectura actual:

Trobar un algoritme de planificació òptim de UET per a tres processadors en restriccions de precedència

Font:

• Marc Chardon, Aziz Moukrim
• The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders, SIAM J. Discrete Math, Volume 19 (2005), Number 1 pp. 109-121.

Descripció: Un problema de planificació de unit-execution-clave (UET) conté tasques totes elles d'igual llongitut. Quan hi ha restriccions de precedència entre les tasques, llavors significa que existix un grafo dirigit entre les tasques UET. Per a començar una tasca totes les seues predecessores deuen haver acabat. Dos algoritmes òptims es coneixen per a tasques UET de 2 processadors. [CoffmanGraham72] [GareyJohnson76].

Importància: Este problema és equivalent a planificar instruccions en una computadora superscalar i planificar tasques paraleles de forma òptima en un multiprocessador en 3 processadors.

Conjectura actual:

Vore també

• Problemes no resolts de la matemàtica
• Problemes no resolts de l'ingenieria de software