# 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&#x20;
* 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