list-of-unsolved-problems

Unsolved problems

Millennium Prize Problems

  • P vs NP (Polynomial time vs Nondeterministic Polynomial time)

  • Hodge conjecture

  • Poincaré conjecture (solved)

  • Riemann hypothesis

  • Yang–Mills existence and mass gap

  • Navier–Stokes existence and smoothness

  • Birch and Swinnerton-Dyer conjecture

Unsolved problems in CS

https://www.wikiwand.com/en/List_of_unsolved_problems_in_computer_science

Computational complexity

  • Relationship between BQP and NP (BQP, Bounded-error Quantum Polynomial time)

  • 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

P vs NP for specific algorithmic problems

  • Can integer factorization be done in polynomial time on a classical computer

  • Can integer factorization be considered to be 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[1]

  • Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time[2]

  • Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time[3]

Algorithmics

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

Natural Language Processing

  • Is there any perfect syllabification algorithm in English language

  • Is there any perfect stemming algorithm in English language

  • Is there any perfect POS tagging algorithm in English language

Programming language theory

  • POPLmark

  • Barendregt–Geuvers–Klop conjecture

Other problems

  • Aanderaa–Karp–Rosenberg conjecture

  • Generalized star height problem

  • Separating words problem

  • Possibility of hypercomputation

PreviousList of mathematical theoriesNextLists of problems in math

Last updated