List of unsolved problems in computer science

From Wikipedia, the free encyclopedia

This article is a list of unsolved problems in computer science. A problem in computer science is considered unsolved when no solution is known, or when experts in the field disagree about proposed solutions.

Computational complexity

Polynomial versus non-polynomial time for specific algorithmic problems

Other algorithmic problems

Programming language theory

Other problems


  1. ^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete", SIAM Journal on Discrete Mathematics, 23 (2): 909–939, MR 2519936, doi:10.1137/070687256 .
  2. ^ Demaine, Erik D.; O'Rourke, Joseph (2007), "24 Geodesics: Lyusternik–Schnirelmann", Geometric folding algorithms: Linkages, origami, polyhedra, Cambridge: Cambridge University Press, pp. 372–375, ISBN 978-0-521-71522-5, MR 2354878, doi:10.1017/CBO9780511735172 .
  3. ^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Simultaneous graph embeddings with fixed edges", Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers, Lecture Notes in Computer Science, 4271, Berlin: Springer, pp. 325–335, MR 2290741, doi:10.1007/11917496_29 .

External links

  • Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
  • The RTA list of open problems – open problems in rewriting.
  • The TLCA List of Open Problems – open problems in area typed lambda calculus.
Retrieved from ""
This content was retrieved from Wikipedia :
This page is based on the copyrighted Wikipedia article "List of unsolved problems in computer science"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA