SoylentNews is people
SoylentNews
Mystery Math Whiz and Novelist Advance Permutation Problem
A new proof from the Australian science fiction writer Greg Egan and a 2011 proof anonymously posted online are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years.
On September 16, 2011, an anime fan posted a math question to the online bulletin board 4chan about the cult classic television series The Melancholy of Haruhi Suzumiya. Season one of the show, which involves time travel, had originally aired in nonchronological order, and a re-broadcast and a DVD version had each further rearranged the episodes. Fans were arguing online about the best order to watch the episodes, and the 4chan poster wondered: If viewers wanted to see the series in every possible order, what is the shortest list of episodes they'd have to watch?
In less than an hour, an anonymous person offered an answer — not a complete solution, but a lower bound on the number of episodes required. The argument, which covered series with any number of episodes, showed that for the 14-episode first season of Haruhi, viewers would have to watch at least 93,884,313,611 episodes to see all possible orderings. "Please look over [the proof] for any loopholes I might have missed," the anonymous poster wrote.
The proof slipped under the radar of the mathematics community for seven years — apparently only one professional mathematician spotted it at the time, and he didn't check it carefully. But in a plot twist last month, the Australian science fiction novelist Greg Egan proved a new upper bound on the number of episodes required. Egan's discovery renewed interest in the problem and drew attention to the lower bound posted anonymously in 2011. Both proofs are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years.
Mathematicians quickly verified Egan's upper bound, which, like the lower bound, applies to series of any length. Then Robin Houston, a mathematician at the data visualization firm Kiln, and Jay Pantone of Marquette University in Milwaukee independently verified the work of the anonymous 4chan poster. "It took a lot of work to try to figure out whether or not it was correct," Pantone said, since the key ideas hadn't been expressed particularly clearly.
Now, Houston and Pantone, joined by Vince Vatter of the University of Florida in Gainesville, have written up the formal argument. In their paper, they list the first author as "Anonymous 4chan Poster."
"It's a weird situation that this very elegant proof of something that wasn't previously known was posted in such an unlikely place," Houston said.
[...] If a television series has just three episodes, there are six possible orders in which to view them: 123, 132, 213, 231, 312 and 321. You could string these six sequences together to give a list of 18 episodes that includes every ordering, but there's a much more efficient way to do it: 123121321. A sequence like this one that contains every possible rearrangement (or permutation) of a collection of n symbols is called a "superpermutation."
The story then describes parallels with the "Asymmetric" (aka weighted) traveling salesman problem as well as the fortuitous connections which led researchers to work together in finding calculations of upper and lower bounds for an arbitrary number of episodes. You'll have to RTFA to learn how many episodes you'd need to watch to view them in all possible orders.
(Score: 2) by acid andy on Friday November 09 2018, @02:26AM (2 children)
From TFA:
And:
The traveling salesmen problem is well known as an NP-complete [wikipedia.org] problem, which means that if an algorithm can be found to solve it quickly (in polynomial time) in all cases, then P=NP [wikipedia.org], meaning a huge class of problems will be able to be solved just as quickly. Which leaves me wondering whether being able to "completely nail down this puzzle" will reveal a way to do just that. If it does, it would have huge implications for computer science.
If a cat has kittens, does a rat have rittens, a bat bittens and a mat mittens?
(Score: 1) by DECbot on Friday November 09 2018, @03:36AM (1 child)
You ended your history of the world prematurely stopping where you did. The cold war ended with the creation of the intertubes. Let me explain, Alberto Eye-in-Steiner theorized a system could collect enough data points that it would reach critical mass and start collecting data on its own--where data was entered into the terminal never leave. There would be so much data none could escape to the terminal. He called it a black data hole cause the terminal screen would remain black. Stevie Hawkeye expanded the theory to show that some data did escape the data black holes as metadata in the syslog assessable in another terminal on the system. However, the interesting part is the data actually leaks from the black hole as background radiation, AKA Hawkeye Radiation. This radiation of the intertubes has caused global warming which has since thawed the Cold War and popularised skimpy, breathable clothing. 'Marycan has since weaponized calculators connected to the intertubes to inflict goatse on third world countries not interested in bikinis, board shorts, Birkenstocks and hot wars.
cats~$ sudo chown -R us /home/base
(Score: 1) by DECbot on Friday November 09 2018, @05:35AM
Whoops, execution on my behalf. My comment was in response to this comment [soylentnews.org]. I blame trying to post comments during a rough landing and slow, intermittent internet. Sorry about any confusion.
cats~$ sudo chown -R us /home/base