In a Paper of 1985The scientist on the computer Andrew Yao. He also said that, in the worst case, where you look for the last remaining open place, you can't do better than x. For 40 years, most computer scientists have assumed that Yao's speculation is true.
Krapivin was not prevented by conventional wisdom for the simple reason he did not know it. “I did this without knowing about Yao's imagination,” he said. His exploration of small advice leads to a new type of hash table – one that does not rely on equal trial. And for this new hash table, the time required for the worst case of queries and insertions is proportional to (log x)2—Far faster than x. This result is directly opposed to Yao's speculation. Farach-Colton and Kuszmaul helped Krapivin show that (Log x)2 is the best, unmatched tied for the popular type of hash table that Yao wrote.
“This result is nice to respond to it and solve such a classic problem,” said Guy Blelloch of Carnegie Mellon.
“Not only are they not approved [Yao’s conjecture]they also found the best possible answer to his question, ”says SEPEHR ASSAD of the University of Waterloo. “We can leave another 40 years before we know the right answer.”
In addition to denial of Yao's imagination, the new paper also contains what many consider to be more surprising results. It pertains to a relevant, though slightly different, situation: in 1985, Yao looked not only in the worst case for queries, but also at the average time taken in all possible queries. He proved that the hash tables with some possession – including those labeled “greedy,” which means new elements must be placed in the first available area – will never achieve an average time better than lying x.
Farach-Colton, Krapivin, and Kuszmaul want to see if the same limit is also applied to desks that are not serious hash. They show that it's not by giving a counterexample, a non-genened hash table with average query time better, better than log x. In fact, it is not dependent x At all. “You're getting a number,” Farach-Colton said, “something consistent and not depending on how serious the hash table is.” The fact that you can achieve a constant average query time, regardless of the fullness of the hash table, is completely unexpected – even with those with -set itself.
Team results may not lead to any immediate applications, but that doesn't matter, Conway said. “It is important to understand these kinds of data structures that are better. You never know when a result like this will open something that gives you better in practice.”
Original story Na -print with permission from How much magazinean independent publication of the editorial of Simons Foundation that the mission is to enhance the public understanding of science by occupying research development and math trends and the sciences of physical and life.
