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