Lista de problemas computacionales sin resolver
Este artículo es una lista de problemas no resueltos importantes en informática . Un problema en informática se considera no resuelto cuando no se conoce ninguna solución o cuando los expertos en el campo no están de acuerdo sobre las soluciones propuestas.
Complejidad computacional
Tiempo polinomial versus tiempo polinomial no determinista para problemas algorítmicos específicos
Otros problemas algorítmicos
Teoría de lenguajes de programación
Otros problemas
Referencias
- ^ Fellows, Michael R. ; Rosamond, Frances A. ; Rotics, Udi; Szeider, Stefan (2009), "El ancho de camarilla es NP-completo" (PDF) , SIAM Journal on Discrete Mathematics , 23 (2): 909–939, doi :10.1137/070687256, MR 2519936, S2CID 18055798, archivado desde el original (PDF) el 2019-02-27.
- ^ Demaine, Erik D.; O'Rourke , Joseph (2007), "24 Geodésicas: Lyusternik–Schnirelmann", Algoritmos de plegado geométrico: Enlaces, origami, poliedros , Cambridge: Cambridge University Press, págs. 372–375, doi :10.1017/CBO9780511735172, ISBN 978-0-521-71522-5, Sr. 2354878.
- ^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Incrustaciones simultáneas de grafos con aristas fijas" (PDF) , Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Noruega, 22-24 de junio de 2006, Documentos revisados (PDF) , Lecture Notes in Computer Science, vol. 4271, Berlín: Springer, pp. 325–335, doi :10.1007/11917496_29, ISBN 978-3-540-48381-6, Sr. 2290741.
Enlaces externos
- Problemas abiertos en torno a algoritmos exactos por Gerhard J. Woeginger , Discrete Applied Mathematics 156 (2008) 397–405.
- La lista de problemas abiertos de la RTA – problemas abiertos en la reescritura .
- Lista de problemas abiertos de TLCA: problemas abiertos en cálculo lambda de tipo área .