Content deleted Content added
m Open access bot: arxiv updated in citation with #oabot. |
LouScheffer (talk | contribs) →Hash tables: Add connectivity in undirected graphs. |
||
Line 67:
| class = cs
}}</ref> But it remains purely theoretical: "Despite the new hash table’s unprecedented efficiency, no one is likely to try building it anytime soon. It’s just too complicated to construct."<ref name="OptimalBalance">{{cite web | last=Nadis | first=Steve | title=Scientists Find Optimal Balance of Data Storage and Time | website=Quanta Magazine | date=8 February 2024 | url=https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/ | access-date=12 February 2025}}</ref> and "in practice, constants really matter. In the real world, a factor of 10 is a game ender.”<ref name="OptimalBalance"/>
=== Connectivity in undirected graphs ===
Connectivity in undirected graphs (known as USTCON) is the problem if deciding if a path exists between two nodes in an undirected graph, or in other words, if they are in the same connected component. If you are allowed to use <math>O(\text{N})</math> space, polynomial time solutions such as [[Dijkstra's algorithm]] have been known, and commonly used, for decades. But for many years it was unknown if this could be done deterministically in <math>O(\text{log N})</math> space, though it was known to be possible with randomized algorithms.
In 2004, a breakthrough paper by [[Omer Reingold]] showed that USTCON is in fact in '''[[L (complexity)|L]]''', the class of problems that can be solved deterministically in <math>O(\text{log N})</math> space.<ref>{{citation
| last = Reingold | first = Omer | author-link = Omer Reingold
| doi = 10.1145/1391289.1391291
| issue = 4
| journal = [[Journal of the ACM]]
| mr = 2445014
| pages = 1–24
| title = Undirected connectivity in log-space
| volume = 55
| year = 2008}}.</ref>
However, despite the asymptotically better space requirement, [[SL (complexity)#Important results|this algorithm is galactic]]. The constant hidden by the <math>O(\text{log N})</math> is so big that in any practical case it uses '''more''' memory than the well known <math>O(\text{N})</math> algorithms, plus it is exceedingly slow. So despite being a landmark in theory (more than 1000 citations as of 2025) it is never used in practice.
== References ==
| |||