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 -> 93884331311
So the conjecture here is that the length of the minimal superpermutation is
n! + (n-1)! + (n-2)! + fib(2n - 6).
The only thing to be said in favour of this idea is that it lies between the known lower and upper bounds, so we can’t yet prove it’s wrong. But there is no reason at all to expect Fibonacci numbers to appear in this context.
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)
for n > 3. We can’t prove this either, but at least there is reasonable evidence for it.
For n = 7, their formula gives 5901 and yours gives 5907. How feasible would it be to verify which one's correct? Exhaust every 5901-long sequence? Or is there some smarter way?
I wonder if some day, some one will anonymously post solution to the P vs NP problem, without fully understanding the scope and effect of the solution on the world.
Some 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.
This almost certainly won't happen. First, because "P vs NP" is a very well-studied problem and many complex technical constraints have been proved about what kinds of things can and cannot be part of "P" algorithm for an NP-complete problem. There's no way to be educate enough to be able express something that could possibly be a well-formed proof (and not made meaningless by its vaguess) without knowing enough to navigate these concerns and therefore appreciating the magnitude of the problem.
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.
Out of curiosity, if someone proved P to not equal NP, what kind of scope and effect would it bring to the world outside academia? P == NP would obviously be a world-transforming proof
Right. The important thing about the Clay Mathematics Millenium Prize is that it is a set of well-chosen SMART-ish goals. They want to incentivize work on really hard fields of mathematics but they have tried to do this by choosing results that are each not too intimidating. The Navier-Stokes prize, for example, allows you to assume all of the nicest features of Navier-Stokes problems in practice -- basically all of the fluid flows are well below supersonic and are occurring in highly homogeneous, nice fluids -- and ask the most basic mathematical question: does a smooth solution to these equations always exist? That question by itself is not so important, but it's specific and measurable. But it's a bit of a "reach" -- you would have to have some cutting insight about turbulence in order to answer this question one way or the other. That cutting insight is what they're trying to incentivize.
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."
It would probably give us some new insight on what computation actually is. Our inability to formally proof class separation suggests we're missing something.
RSA algorithm is based upon factorization, reverse problem for which is in NP. If a solution's difficulty is a low degree polinom (3 or lower, but I might be wrong) it could be used to get private keys from public ones in a matter of days.
The proof itself would not give factorization algorithm.
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.
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: