P < NP In Our Stockings?
Brute force wins—sometimes
|
| Teespring.com source |
Santa Claus is on the way to visit those of us who have been good.
Tonight is Christmas Eve, and we want to thank everyone who has been supporting Ken and me at GLL.
Whether or not you believe in Santa Claus, whether or not you celebrate Xmas, we should agree that this has been some year.
Indeed the the whole Santa Claus issue raises some questions about truth telling. Children are typically told by their parents that Santa is real; tonight you can “watch” his progress as he travels around the world. Dr. Anthony Fauci even said he traveled to the North Pole to give Santa the new Covid-19 vaccine.
This raises some objections to presenting Santa Claus as a real person, rather than a story:
- That lying is normally bad.
- That parents intentionally lying to their children promotes distrust.
- That it promotes selfishness, greed, and materialism.
- That it associates good behavior with being materially rewarded with presents from Santa Claus.
- That tricking children into believing falsehoods interferes with the development of critical thinking.
Most agree that it is harmless, but see this for more on the controversy. Ken finessed it by “superposing” the real Saint Nicholas on what told his children.
Or read this book on The Indisputable Existence of Santa Claus: The Mathematics of Christmas by Hannah Fry and Thomas Evans.
P 
NP
The belief that P is weaker than NP, that there is no efficient algorithm for many problems, is perhaps our version of Santa Claus. We cannot prove it, we cannot see how to even really approach it.
But most of us believe that a resolution is presently out there, and that says there is no efficient algorithm for SAT and other NP-complete problems. Is this a story we tell each other like Santa Claus: Is P
P 
NP
Well not really: P is not equal to NP yet. But there are many important examples of hard problems that are solved every day. These problems are solved even though they are believed to be hard to solve.
The algorithms that are used are brute force. The algorithms just try all the possible solutions and keep checking to see if this guess is correct. While complexity theory is filled with clever algorithms for hard problems that:
- Solve special cases;
- Give approximation solutions;
- Solve some of the time;
- And so on.
Often only a perfect solution in the general case is what we sometimes needed. Two important examples of this are:
- Bitcoin mining;
- Password cracking.
The first of these can be as precious as a diamond, but the latter is a lump of coal when it happens to us.
Password Cracking
A password is checked by a system by using a password file 
![\displaystyle [name, h(name,p)].](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Bname%2C+h%28name%2Cp%29%5D.+&bg=ffffff&fg=000000&s=0&c=20201002)
A user who claims to be 
Here 
The hope is that it is hard to invert the hash function 
will check correctly.
Even with random passwords cracking them by brute force is possible
Graphics processors can speed up password cracking by a factor of 50 to 100 over general purpose computers for specific hashing algorithms. As of 2011, available commercial products claim the ability to test up to 2,800,000,000 passwords a second on a standard desktop computer using a high-end graphics processor. Such a device can crack a 10 letter single-case password in one day.
This is an amazing result. The algorithm that breaks passwords, the cracker, is just brute force. But the cleverness is all in the implementation. The cleverness is using GPU’s or FPGA’s to make the algorithm—brute force or not—run so fast. Here GPU’s are graphics processors and FPGA‘s are field programmable arrays. Both of these devices are hardware that is well matched to computing the hash functions that are used. See this Hackaday item for details.
Open Problems
Have a safe Xmas, and a safe rest of the year. Take care all.
Dick and Ken.
This has been a hard year for almost to everyone. However, for me it has been different, because one of the author of this blog has shown interest in my work. We started discussing my P = NP work in the summer:
https://doi.org/10.5281/zenodo.3355776
Dick checked my work, but when we got to the end (exactly in Theorem 12), he stopped suddenly the revision. I sent him many emails looking for a reason, but no reason was given. Two month later he asked me how was the paper and I told him that I sent it to STACS2021. In STACS2021 I received only one rejected review and I convinced them my arguments were right in the rebuttal (my response was correct and the rejected review was invalid). This was the final response:
“We misunderstood one of your claims. You are not computing the weighted densities of states, but only the sum over it. Then the construction as claimed in the rebuttal works. However, the sum of weighted densities is not known to be NP-complete. You give some arguments in Theorem 12 but they are not complete. In particular the claim that when one sum is smaller than the other, then this is also true for the weighted sum, has no proof and is simply wrong.”
In that same month, Dick decided to participate as an author in this paper about the Riemann Hypothesis:
https://doi.org/10.5281/zenodo.3648511
He made a better approach and improvement to the paper (Important-> this improvement is not in the version I’m sharing to you). However, I was sick in that moment and Dick had personal issues. Due to the circumstances we stopped again the communication and right now the paper has nothing of the contribution of Dick and has new things that Dick has not checked. I sent the paper to the journal Forum of Mathematics, Sigma and I received this answer:
“Because so many authors have submitted false solutions to the problem addressed in your manuscript, we can only consider such solutions if the exposition is exceptionally clear. If you are convinced that your solution is correct, and wish to continue to pursue publication, then you should have someone else (for instance a mathematically literate friend or colleague, or perhaps a mathematician at a local university) read your manuscript and give you suggestions for improving the readability. You should submit your manuscript again to a journal only if that person is able to understand your manuscript well enough to certify its correctness.”
End of this story.
With this short and real story, I want to thank Dick for his support, for his patience on my mood and for the time he used with me. I think it is also a good story to share for those amateurs who like me are dreaming and working hard (I have just wanted to send a message to them: nobody say it will be easy, but at least it could be worth even if you fail).
Merry Christmas,
Frank
“These problems are solved even though they are believed to be hard to solve.”
No. *Single instances* of these problems are solved. If you are only worried about solving one particular instance (or two, or three), your program (if it halts) has running time O(1). It’s only when you want to solve them all (actually, just infinitely many), and there’s a parameter n that varies, that P and NP become relevant.
For example, the Travelling Salesman Problem on 50 cities can be solved using brute force, and its running time is O(1). Granted, the constant is large (50! * 50 * 3 arithmetic operations ought to do it), but there’s no n to vary, so P and NP are irrelevant.
Isn’t P=NP more like equivalent to the existence of Santa? We keep on looking for an algorithm, but no one has found one (yet).
The situation might be more complicated; it might be able to prove that there is an algorithm but you can’t explicitly show it. (I doubt that the P=NP algorithm would be like this, though.)
For instance, take a graph [network] and look at its embeddings in 3-D space. There might be two cycles which in this embedding are two linked simple closed curves, or not. Robertson and Seymour proved that there is an algorithm to determine whether this is the case, but (the last time I checked up on it) no one had actually produced an explicit algorithm. Furthermore, the RS algorithm runs in less than cubic (O(N^3)) time, so it’s even efficient!
(Very brief explanation: They showed that the set of solutions is “minor closed”, and that there is a finite set of graphs such that any “linked embedding” contains one of them as a minor, so you just test your graph to see if it contains one of these graphs. There’s a similar algorithm for planarity, where the set contains the two elements K(5) and K(3,3).)
Is there anyone really looking for Santa Claus?
Sounds like the great vaccine anti vaccine debate to me. If p equaled np you could simply tell people to stop being stupid.
Open problem ‘Have a safe Xmas, and a safe rest of the year. Take care all.’.