Mystery Math Whiz and Novelist Advance Permutation Problem
quantamagazine.org
quantamagazine.org
We’re making progress pretty rapidly at the moment. The lower bound has recently been improved (by one), and Greg Egan’s construction has been shown to be the best possible under certain conditions.
I think it’s reasonably likely – though definitely not certain – that we will have a complete solution within weeks.
0. https://groups.google.com/forum/?nomobile=true#!forum/superp...
In the article they say "The factorial rule predicts that to watch six episodes in every possible order should require 873 episodes, but Houston found a way to do it in 872. And since there is a simple way to convert a short superpermutation on n symbols into a short superpermutation on n + 1 symbols, Houston’s example meant that the factorial rule fails for every value of n above 6 too."
I don't quite get this. Is there an inductive proof you can use as a construction to reduce the length for subsequent N? Would love to see a birds-eye view of the intuition of this.
It just turned out that the conjecture was easily disproved by that simple rule construction.
The construction is described in various places online. I like Greg Egan’s description here: http://www.gregegan.net/SCIENCE/Superpermutations/Superpermu...
Sorry for the delayed reply. I was stymied by my aggressive noprocrast setting.
Do you see it as a variation on the one in the article?
https://www.reddit.com/r/dailyprogrammer/comments/8rcjx0/201...
"Given an input set of strings, produce an output string. Every string in the input must be an anagram of some slice of the output. A slice in this context is a series of characters from the string separated by a fixed amount (i.e. anything that can be formed using Python's s[a:b:c] syntax). It's different from a substring in that you're allowed to skip characters, as long as you skip the same number of characters on each step."
Obviously that doesn’t mean we can’t find nice algorithms that work well in particular cases, but I bet it’s hard to prove that a solution is the best possible.
What makes the minimal superpermutation problem different is that we’re trying to pack together the set of ALL permutations of some number of symbols, so the set of strings has a lot of known symmetry and structure we can take advantage of. In this case I hope it will be possible to find a general solution that we can prove is the best possible.
For every "undiscovered genius whose treatise finally gets a fair shake", there are hundreds of cranks, trolls, or attention-seekers who -- freed of reputation -- can create a hundred mutated iterations of low-quality stuff until something takes off just due to random luck. Sockpuppets are another concern, since it's easier to fabricate a consensus approval.
None of this is especially new either -- BBSes and usenet and web-forums have been around for decades.
Perhaps initially, but an equally effective currency is shock/bait value. And when reply counts are the only way to keep threads alive, it's often the most provocative but not necessarily highest quality threads that garner replies and snowball. In fact in the case of many boards it often leads a pool of low quality drudge as the user count increases.
real currency on anonymous
message boards is the quality
and content of your ...
Scholarly tools like anonymous peer review, double blind reviews, double blind experiemnts, anonymous grading etc all work precisely because of anonymity.
A key mechanisim behind the positive qualities of anonymity is that the anonymous author no longer must fear punishment for the anonmous speech. The key invention here was the invention of writing, which enabled the separation (in space and time) between author and audience. This was amplified by the invention of the printing press (which amphified the audience), and later the internet.
I'm not a historian of writing, but I suggest the following hypothesis: contemporary arguments against online anonymity (e.g. leads to trolling etc) are structurally somewhat similar to (but not idential with ) historical arguments against writing and the printing press.
This is not quite true yet. An absolutely minuscule fraction of math papers published today involve machine proofs.
Which means that the proof doesn't have to be machine-checkable; in fact, it'd be less effective at doing its job if it included every trivial step. It's not code. It's pseudocode; the purpose is to communicate to humans.
As a working mathematician, I wholeheartedly agree with the second part of the quoted sentence! But I think that the first part isn't quite right: The function of proofs to determine truth is extremely important, especially considering that, especially in pure mathematics, we often can't check our results in any other manner (like conducting physical experiments or checking many cases with the computer).
Bad experiences with proofs which later turned out to be faulty led Voevodsky to initiate his univalent foundations program (also called homotopy type theory), where all results should be checked by the computer. (For the particular area he was working on, no existing theorem prover turned out to be sufficient. He made a breakthrough in finding a new foundation to base theorem provers on, which made it possible to formalize results in his area of mathematics not only in principle, but also in practice.)
The hope is also that with computer-checked proofs, we can advance to new areas of mathematics which are currently inprenetable to our puny human minds. I'm very much looking forward to this future!
You can learn more about Voevodsky's vision in slides of him and in a recorded lecture: https://www.math.ias.edu/~vladimir/Site3/Univalent_Foundatio... https://www.youtube.com/watch?v=O45LaFsaqMA
https://www.microsoft.com/en-us/research/uploads/prod/2016/1...
A good friend of mine creates those as a hobby: https://pwacker.com/
There are also a bunch of rather unfortunate new comments at the end of the archive from the last few days, when the link has obviously gained some public attention. However, in the midst of all the new nonsense, the recent one that begins "I think I solved it" is pretty interesting:
--Anonymous Sun Oct 28 14:10:06 2018--
I think I solved it.
First calculate the max string which is the number of permutations multiplied by n.
Then divide the max string by n - 1
Then add to the answer the fibonacci number located at 2(n-3)
int max_string = n! * n;
int answer = max_string / (n - 1);
answer += fib(2(n-3));
Example for n = 5;
max_string = 5! * 5 = 600
answer = 600 / 4 = 150
answer += fib(2(5-3)) = fib(4) = 3
answer = 153
Here is the first 14 using this method:
2 -> 3
3 -> 9
4 -> 33
5 -> 153
6 -> 872
7 -> 5901
8 -> 46135
9 -> 408384
10 -> 4032377
11 -> 43909467
12 -> 522549784
13 -> 6745945965
14 -> 93884331311Some times not knowing the history and hardness of a tasks helps in a novice attempting an impossible task, and arriving at the solution, completely ignorant of the history of the problem.
Even if P = NP, prime factorization can be very time consuming to solve. The prime factorization problem is in the NP class, but we don't know if it is NP-hard.
What would be very interesting - and likely give pretty deep insights into the very nature of computation - would be how exactly they proved it.
P vs NP is the same: if solutions to a problem are easy to check, is there always some better way to analyze the mechanics of the checker to make those solutions easy to find, so that we aren't stuck with brute-forcing it? Whether the answer goes one way or the other, the point is that solving the problem would have to provide some insight to the effect of "here is a periodic table of elements for all of the 'easy' algorithms -- and here are the properties of all the 'molecules' made by combining those building blocks." And only once someone advances our understanding with those cutting insights can we say "yes we can always reach into the verification mechanism to understand it well enough to build a better-than-brute-force algorithm" or "no, here is such a thing that algorithms cannot do, it's not just that I am not smart enough to find a way for them to do this -- they are fundamentally incapable of doing it faster."
That's one of best motto I've ever heard!
Second, because the proof won't be useful outside of arcane theory. If P != NP, that verifies something everyone already asumes, so it wouldn't change much except for abstract curiosity of a few experts able to comprehend the complexity of the meaning.
n! * n / (n-1)
= n^2 * (n-2)!
= n * (n-1 + 1) * (n-2)!
= n! + n * (n-2)!
= n! + (n-1 + 1) * (n-2)!
= n! + (n-1)! + (n-2)!
n! + (n-1)! + (n-2)! + fib(2n - 6).
The most plausible conjecture we have right now is that the length of the minimal superpermutation is
n! + (n-1)! + (n-2)! + (n-3)! + (n-4)
On the other hand, I think we will soon have an improved lower bound that is strong enough to refute this formula.
The short description is: a project using a child's radio-toy to open a garage door, without knowing the correct code.
These are slightly different problems though because you need 111 in this case but not in the one this article is about. It's much easier (according to my mathmo friend who solved it).
> 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.
Rephrasing it a bit, the problem is generating the shortest string of tokens (with repetition of the N tokens) in which every possible permutation of those N tokens is a substring.
Simulated beings are a repeated topic in Egan's stories. Some of them are freely available online, for instance https://www.gregegan.net/PLANCK/Complete/Planck.html (where simulated beings create clones of themselves which are to fall into a black hole, hoping to gain insights on fundamental physics) and https://www.gregegan.net/INCANDESCENCE/00/Crocodile.html (where a couple, after having lived for more than ten thousand years, decides to embark on a final adventure, leaving all loved ones behind because of differences in time perception).
These techniques can be orders of magnitude more efficient than a standard hyperparameter search and really cut down the barrier to entry for these types of results.
Somehow I suspected it was Greg Egan before clicking on that link.
> Within a day or two, he had come up with a new upper bound on the length of the shortest superpermutation for n symbols: n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3
> The anonymous 4chan poster’s lower bound, meanwhile, was tantalizingly close to the new upper bound: It works out to n! + (n – 1)! + (n – 2)! + n – 3
IE: The upper bound has been lowered to
n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3
n! + (n – 1)! + (n – 2)! + n – 3
The lower bound is achieved when the permutations overlap perfectly, e.g. when n = 2:
1, 2, 1
The upper bound is simply the concatenation of all permutations. You can get lower than this by exploiting the fact that some permutations' suffixes are other permutations' prefixes.
However, you can do much better, exploiting overlap, using only 93,884,313,611 episodes, which is really quite remarkable, because it is just 1.08 episodes per permutation.
Example with 3 (from the article):
3! = 6 permutations
Bad way to watch all: concatenate all permutations
A) 123 132 213 231 312 321 (= 3*6 = 18 episodes, or 3 episodes per permutation)
Good way to watch all permutations:
B) 123121321 (= 9 episodes, or 1.5 episodes per permutation)
Note that each of the permutations above in A is contained in the string at B).
See here: http://www.njohnston.ca/2014/08/obvious-does-not-imply-true-...
It has been asked in real interviews
The solution to this problem is given by de Bruijn sequences: https://en.wikipedia.org/wiki/De_Bruijn_sequence
And can confirm that at least one FAANG company has asked this in a real interview.
And if so - if someone solves this programming task on leetcode have they not then also solved the permutation problem from OP?
(The submission title is by far the biggest influence on what comments get posted.)