What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the decision tree complexity of the MST…
What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, 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.
Open the “Other algorithmic problems” section on Wikipedia →
Source: List of unsolved problems in computer science (CC BY-SA 4.0)