Unsolved Problems in Algorithms

Algorithms seem to be simple but there are several unsolved problems in Algorithms. We have listed some of the easiest sounding unsolved problems like Dynamic Optimality Conjecture which you should know.

  1. Do splay trees perform as well?
  2. All Pairs Shortest Paths
  3. Fastest matrix multiplication
  4. Time complexity of Shellsort
  5. Exponential time hypothesis
  6. Complexity of minimum spanning tree

Some of the official Unsolved Problems in Algorithms are:

  • Dynamic Optimality Conjecture
  • Traversal Conjecture
  • Deque Conjecture
  • Split Conjecture

1. Do splay trees perform as well?

In this part, we cover 4 related conjectures:

  • Dynamic Optimality Conjecture
  • Traversal Conjecture
  • Deque Conjecture
  • Split Conjecture

Yes, Splay Tree is a common Binary Search Tree (BST) but not everything is known about it. One of the challenging problem is:

Do splay trees perform as well as any other binary search tree algorithm?

This is known as "dynamic optimality conjecture" and is mentioned in the paper by Sleator and Tarjan on Splay Trees.

The conjecture claims that Splay Trees perform as well as other Binary Search Trees with a constant factor. Note that the performance of different operations of Splay Tree has been proven but this conjecture is still unproven.

The exact statement of Dynamic Optimality Conjecture is:

Let A be any binary search tree algorithm that accesses an element x by traversing the path from the root to x at a cost of d(x)+1 and that between accesses can make any rotations in the tree at a cost of 1 per rotation. Let A(S) be the cost for A to perform the sequence S of accesses. Then the cost for a splay tree to perform the same accesses is O[n + A(S)].

There are 3 more conjectures that are related to this Conjecture:

  • Traversal Conjecture
  • Deque Conjecture
  • Split Conjecture

Traversal Conjecture claims that if there are two splay trees with the same elements, then traversing a specific sequence of elements in preorder should be linear for both trees.

The official statement is:

Let T1 and T2 be two splay trees containing the same elements. Let S be the sequence obtained by visiting the elements in T2 in preorder (i.e., depth first search order). The total cost of performing the sequence S of accesses on T1 is O(n).

Deque Conjecture

Let S be a sequence of m double-ended queue operations (push, pop, inject, eject). Then the cost of performing S on a splay tree is O(m + n).

This sounds simple but is challenging.

Split Conjecture

Let S be any permutation of the elements of the splay tree. Then the cost of deleting the elements in the order S is O(n).

2. All Pairs Shortest Paths

Can All Pairs Shortest Paths be computed in strongly sub-cubic time, that is, in time O(V^(3−ϵ)) for some ϵ>0?

Currently, we can find the shortest path between all pairs of vertices in O(V^3) time. The problem is to prove whether we can do this in polynomially better time.

The progress is as follows for undirected graphs:

  • Floyd Warshall algorithm O(V^3)
  • Seidel's algorithm O(V^w * logV)
  • William 2014 O(V^3 / 2^((logN)^0.5))
  • Pettie and Ramachandran 2002 O(EV log a(E,V))
  • Thorup 1999 O(EV)

The progress is as follows for directed graphs:

  • Floyd Warshall algorithm O(V^3)
  • Williams 2014 O(V^3 / 2^((logN)^0.5))
  • John Dijkstra O(EV + V^2 logV)
  • Pettie 2004 O(EV + V^2 log log V)
  • Hagerup 2000 O(EV+V^2 loglogV)

3. Fastest matrix multiplication

What is the fastest algorithm for matrix multiplication?

Currently, matrix multiplication algorithm with best asymptotic complexity runs in O(n^2.3728596) time. It was invented by Josh Alman and Virginia Vassilevska Williams.

It is unknown what is the optimal or lower limit of doing Matrix Multiplication. Proving the lower limit will be helpful as well.

4. Time complexity of Shellsort

What is the lowest possible average-case time complexity of Shellsort with a deterministic, fixed gap sequence?

The algorithm with the lowest proven time complexity has a time complexity of O(N^4/3).

There are two algorithms by Tokuda, 1992 and Ciura, 2001 whose time complexity is still unknown.

5. Exponential time hypothesis

An unsolved problem is:

Can the edit distance between two strings of length n be computed in strongly sub-quadratic time?

If the strong exponential time hypothesis is false, then only edit distance can be computed in sub-quadratic time.

Exponential time hypothesis states that 3-SAT problem cannot be solved in subexponential time in the worst case.

If this is proven, then the famous P = NP problem will be solved (that is disproven).

6. Complexity of minimum spanning tree

What is the algorithmic complexity of the minimum spanning tree problem?

The core problem to solving this is:
What is the decision tree complexity of the MST problem?

The optimal algorithm to compute MSTs is known, but it relies on decision trees, so its complexity is unknown.

Try these problems and see if you can solve one of these unsolved problems in Algorithms.