User:Erel Segal/Optimal algorithms with unknown runtime complexity
Usually, when there is an algorithm that solves a computational problem, we can calculate its worst-case runtime complexity.
However, there are algorithms which, although we know that they are optimal, we currently don't know their exact runtime complexity! How can this be?
Optimal decision trees
[edit]A decision tree (DT) for solving a computational problem is a tree in which each internal vertex contains a question (such as "is a<b?") and each child corresponds to a possible answer to the question ("yes" or "no"). Each leaf of the DT contains a full solution to the problem. The runtime complexity of a DT is the largest number of queries required to find the MST, which is just the depth of the tree. A DT is called optimal for a problem if it has the smallest depth of all DTs that solve the problem.
The runtime complexity of any computational problem is at least the depth of an optimal decision tree for that problem. Some problems can be solved using the following three-step scheme:
- Build optimal DTs for all possible small instances of the problem;
- Divide a large instance of the problem to several small instances.
- Solve them using the appropriate optimal DTs.
If the run-time of steps 1 and 2 is sufficiently small, then the runtime of the entire algorithm is dominated by step 3. We know that this step is optimal, because no algorithm can be faster than an optimal decision tree; however, we don't know what function describes the depth of the optimal DT as a function of n (the size of the problem), so we don't have a function that describes the runtime complexity of our entire algorithm.
For an example of this peculiar phoenomenon, see Minimum spanning tree#Optimal algorithm.
External links
[edit]Additional examples can be found in: Pettie, S.; Ramachandran, V. (2002). "An optimal minimum spanning tree algorithm". Journal of the ACM. 49: 16. doi:10.1145/505241.505243.