-->

Tuesday, April 17, 2018

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




The Simplest Impossible Problem - A 7-year-old can understand this problem which completely baffles mathematicians. Collatz calculator: http://www.nitrxgen.net/collatz/ https://twitter.com/TPointMath.

  • P versus NP problem (occasionally written erroneously as "P = NP")
  • What is the relationship between BQP and NP?
  • NC = P problem
  • NP = co-NP problem
  • P = BPP problem
  • P = PSPACE problem
  • L = NL problem
  • PH = PSPACE problem
  • L = P problem
  • L = RL problem
  • Unique games conjecture
  • Is the exponential time hypothesis true?
  • Do one-way functions exist?
    • Is public-key cryptography possible?

Polynomial versus non-polynomial time for specific algorithmic problems


P versus NP problem - Wikipedia
P versus NP problem - Wikipedia. Source : en.wikipedia.org

  • Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
  • Is integer factorization NP-complete?
  • Can clustered planar drawings be found in polynomial time?
  • Can the discrete logarithm be computed in polynomial time?
  • Can the graph isomorphism problem be solved in polynomial time?
  • Can leaf powers and k-leaf powers be recognized in polynomial time?
  • Can parity games be solved in polynomial time?
  • Can the rotation distance between two binary trees be computed in polynomial time?
  • Can graphs of bounded clique-width be recognized in polynomial time?
  • Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time?
  • Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time?

Other algorithmic problems


A Computer Science Tapestry - online presentation
A Computer Science Tapestry - online presentation. Source : en.ppt-online.org

  • What is the fastest algorithm for multiplication of two n-digit numbers?
  • What is the fastest algorithm for matrix multiplication?
  • Can the Schwartzâ€"Zippel lemma for polynomial identity testing be derandomized?
  • Can a depth-first search tree be constructed in NC?
  • Does linear programming admit a strongly polynomial-time algorithm? This is problem #9 in Smale's list of problems.
  • What is the lower bound on the complexity of fast Fourier transform algorithms? Can they be faster than O(N log N)?
  • The dynamic optimality conjecture: do splay trees have a bounded competitive ratio?
  • Can we compute the edit distance between two strings of length n in strongly sub-quadratic time, i.e., in time O(n2âˆ'ϵ) for some ϵ>0 ?
  • Is there a k-competitive online algorithm for the k-server problem?
  • Can X + Y sorting be done in strictly less than O(n2 log n) time?
  • How many queries are required for envy-free cake-cutting?
  • What is the lowest possible average-case time complexity of Shellsort with a deterministic, fixed gap sequence?

Programming language theory


NP-completeness - Wikipedia
NP-completeness - Wikipedia. Source : en.wikipedia.org

  • POPLmark
  • Barendregtâ€"Geuversâ€"Klop conjecture

Other problems


P vs NP Problem | Clay Mathematics Institute
P vs NP Problem | Clay Mathematics Institute. Source : www.claymath.org

  • Aanderaaâ€"Karpâ€"Rosenberg conjecture
  • Generalized star height problem
  • Separating words problem
  • Possibility of hypercomputation

References


Computing - Wikipedia
Computing - Wikipedia. Source : en.wikipedia.org

External links


RTS AI Problems and Techniques (PDF Download Available)
RTS AI Problems and Techniques (PDF Download Available). Source : www.researchgate.net

  • 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.

Graph theory - Wikipedia
Graph theory - Wikipedia. Source : en.wikipedia.org

 
Sponsored Links