Open Problems That Might Be Easy
A speculation on the length of proofs of open problems
|
|
Broad Institute source |
Nick Patterson is one of the smartest people I have ever known.
Today I would like to talk about something he once said to me and how it relates to solving open problems.
Nick now works at the Broad Institute on genomic problems—especially large data sets. For decades, he worked as a cryptographer for the British, and then the U.S. He also spent many years with Renaissance Technologies, Jim Simons’s investment hedge fund.
Years ago I consulted regularly at IDA—a think tank for the NSA that was based in Princeton. I cannot tell you what we did, nor what we did not. But I can say we worked on interesting problems in the area of communication. One of the top scientists there was Nick. He was a quite strong chess player, and at tea would often play the other top player at speed chess. I once asked Nick how he would fare against the then world champion Anatoly Karpov. He answered that it would be:
Sack, sack, mate.
I never really believed this. I always thought that he was strong enough to hold out a bit, but perhaps Nick was right. Perhaps it would be over quickly. That Karpov would find a simple, short, demonstration that would wipe Nick out.
But given how smart Nick was I often wondered if he was right when we translate his statement to mathematics:
Can open problems have simple solutions?
Could some open problems fall to: “We know […] and by induction […] we are done”?
Some Short Solutions
Leonhard Euler thought long and hard about possible generalizations of Fermat’s Last Theorem. He was the first to fashion a nearly-correct proof that no cube could be a nontrivial sum of fewer than three cubes. He conjectured that no 4th-power could be a nontrivial sum of fewer than four 4th-powers, no 5th-power a sum of fewer than five 5th-powers, and so on. These cases were open for nearly two centuries, but in 1966, Leon Lander and Thomas Parker used a computer to find
It still took 20 more years for the other shoe to drop on the 
This was the smallest member of an infinite family of solutions found by Noam Elkies—himself a master chess player—though not the smallest overall, which is
The shortest solution to a problem in complexity theory that was important and open for several years was:
Well this needs a little context. If either 
Since it is easy to code 
More recently, a seemingly complicated conjecture by Richard Stanley and Herbert Wilf about permutations was proved in an 8-page paper by Adam Marcus and Gábor Tardos. For any sequence of 
We found the last example highlighted in a StackExchange thread on open problems solved with short proofs. Another we have seen mentioned elsewhere and covered in a post is Roger Apéry’s proof that 
The Euler examples could be ascribed mostly to “computer-guided good fortune” but the other three clearly involve a new idea attached to a crisp new object: an equation or group or matrix construction. We wonder whether and when the possibility of such objects can be “sniffed out.”
Problems Ripe For Short Solutions?
I sometimes wonder if we have missed a simple proof—no, short is a better term—a short proof that would resolve one of our favorite open problems. Here a couple that Ken and I suggest may fall into this category.
Harder Ones?
By contrast, the 3n+1 conjecture of Lothar Collatz does not strike us as a candidate. John Conway proved that related forms are undecidable, and we suspect that it will need deep new knowledge of how intuitively multiplicative properties of integers duck-and-weave under the additive structure.
Regarding the Skolem problem we are on the fence: in a sense it involves DFAs which should be easy, but even for small
Here are four others—what do you think?:
Open Problems
How can we possibly forecast how open an open problem is?
Trackbacks
- undecidability: the ULTIMATE challenge | Turing Machine
- To cheer you up in difficult times 10: Noam Elkies’ Piano Improvisations and more | Combinatorics and more
- 20,000 Comments and More | Gödel's Lost Letter and P=NP
- P vs NP Proof Claims | Gödel's Lost Letter and P=NP
- Sedgewick to Emeritus Status | Gödel's Lost Letter and P=NP
A problem is open if every instance is contained in a neighborhood of instances.
The soul conjecture of Cheeger and Gromoll was open for 22 years and proved by Perelman with a 4-page paper (in which 2 pages are the proof).
http://projecteuclid.org/euclid.jdg/1214455292
Richard and Kenneth,
Interesting.
Some claim that the Lander one is associated with the shortest paper for a proof. Mersenne 67 could be just about the same? (I am not sure of a paper for factoring M67 and have the impression that Cole just gave the talk. Is that right?)
Of course, a solution in a terse form and a full proof paper are different. Here number theoretic ones may always win hands down.
Question: Why P ≠ NP has to go together with ETH? You might just mean “believing in ETH”, a stronger belief? (i.e. not just P ≠ NP but even ETH?)
Maybe, proving the trivial is “the same” as proving ETH? (Am not well versed in this, so this can be just a nonsensical wonder.)
Slightly related is that (one version of) the proof for “P vs. NP” is also short, not as short as the refutation to Euler’s conjecture, as it is not number theoretic and can not be just a few numbers, but should be no more than half a page. See the below challenge to SA.
****
A bet is offered a second time to Scott Aaronson @this place so that we may be able to put the Holy Grail behind us.
Scott,
Let me again propose the bet presented a while back on the existence of a proof for “P vs. NP”.
. . .
How about you and I wage a reasonable US$10,000 . . . ?
R&K, or anybody, interested in being an escrow?
BTW, there is no bias. The bet is for anybody to take, 🙂 but you are forewarned of the sure loss.
— Roielle Hugh
To my knowledge, the slogan “sac, sac, mate” was coined by Rober Fischer in context with his game against Bent Larsen 1958 in Portoroz when he slaughtered his opponent’s Sicilian dragon.
Cristian Calude, in “Evaluating the Complexity of Mathematical Problems” and some other recent related papers, has proposed a method for evaluating the difficulty of some of these problems.
thx for this ref! didnt see it before now! have been espousing a similar view of converting math problems into undecidable problems for years, applying it in the case of the collatz problem, and alas running into strong pushback among CS theoreticians eg on stackexchange cs theory site on that reformulation. personally think it is a dramatic way of unifying CS and mathematics with major potential/ promise and might lead to powerful new theorem proving technology in the not-so-distant future. have a bunch of links on subj & need to write em up sooner or later. was waiting for some kind of sign or breakthrough for that. another paper along the same lines is “problems in number theory from the busy beaver competition”. anyone seriously interested in exploring these ideas please join stackexchange/ theory salon chat room. however calude does not seem to be all that familiar with kolmogorov complexity theory. it appears that even “very small” TMs with very few states eg less than a half dozen are not resolvable by any known methods. so the size of the TM is possibly somewhat misleading/ deceptive on this problem.
I am not sure what is meant by your comment, but I can assure you that Calude is very familiar with Kolmogorov complexity.
>>> . . .
>>> Nell’ora del stupore,
>>> perché, perché, Signor,
>>> ah, perché ti noi rimuneri così?
>>> . . .
****
This coming Monday, PUC logic will stand test.
Folks,
This P/NP saga has induced some spectacular PUC (paradoxical, unconventional, contrarian) logic.
By PUC logic, if everybody out there says that there is no proof, then there must exist one; if it is so difficult as to be beyond everybody, then an actual proof must actually be easily comprehensible; if the proof exists, it must be that everybody can see it and, at the same time, nobody can.
This coming Monday, PUC logic will be put to test.
In a while, I will post a preamble, a light piece that is not to be taken too seriously. Please, do not take offense. We sometimes have to laugh at ourselves.
If anyone, from the preamble, beat me to it, then I probably won’t have to say more.
Let me take a little space here to tell what the bet entails but, instead of anything about the bet, the actual reflection is on the characteristics of the proof.
The US$10,000-bet is for the existence of a proof for “P vs. NP”, satisfying:
1. a version exists of elementary math
2. a version exists of short length
3. a version exists in the public domain
4. a version has existed for a reasonable time
5. a version can demonstrate, using only a P problem
(Details at the end for further clarification.)
Will the proof live up to these characteristics? We will soon find out.
— Roielle Hugh
****
Clarifications:
elementary:
Normal undergraduate level math or below.
short:
It not only has to be terse to capture the entire proof for “P vs. NP”, but also all three questions concerning P, NP and coNP. It will not just fit in the margins of a page in any normal textbook. It should fit in the top margin alone. (Notwithstanding my belief that it should be recognized in seconds.)
in public domain:
One version of the proof in any publicly accessible blog or discussion forum or published conference proceedings will satisfy this.
reasonable time:
Since a bet was made, so we can say a proof existed 30 days prior to the day I made the first offer to SA.
(via) P problem:
This means that only trivial generalization is needed, from a P problem, to arrive at the settlement of “P vs. NP”.
<< End >>
In Preparation For The Settlement Of “P vs. NP”
Since we are on GLL, let me start with something local:
>>> My version is [to] suppose that the alien force asks us to prove that P=NP.
>>> I would say[,] get our best theorists and mathematicians and look for an
>>> algorithm. If on the other hand, they ask for a proof that P ≠ NP, I would
>>> agree with Erdös and suggest we attempt to destroy them.
It will be a heroic fight, but ‘to attempt to destroy them’ actually means getting destroyed. Our only survival is to convince the aliens that we are so inferior to them and can never pose a threat. Yet our situation is dire. Suppose we successfully solve the problem, then we have shown our potentials, which is a threat to them, and we get destroyed. If we present no proof, we get destroyed as well.
How come? Our failure to solve the problem should show our lack of abilities and we should be spared, right? But that is just our way of thinking. We can safely assume, the aliens will just think that we want to out-smart them in faking the inability, because that kind of ability (of faking inability) can always be effortlessly obtained, can’t it?
On the other hand, if the aliens are far superior in abilities in all aspects, including intelligence, we must be superior to them somewhere, right? Yes! -intelligence! I hope, there are no logical errors here.
We can actually be saved by showing a deeper degree of -intelligence than the mere inability to deliver a solution. In fact, we can show a deeper degree of -intelligence, EVEN WITH a solution to “P vs. NP”.
We can obtain a proof and also at the same time show the aliens that we genuinely cannot, even with this proof, prove! We show them, that’s how -intelligent we are, and we can thus be spared. That kind of -intelligence just isn’t possibly fakable.
To show that we can not prove with the proof in our hand is hard work, but we have achieved it. We are left with the easy job of showing a proof.
In the meanwhile, the reader may take a look at this relevant but ‘unclear’ question. Do we rush to ‘proving P small’ without a CLEAR reason?
— Roielle Hugh
****
>>>
>>> I pray you be our eyes,
>>> And watch us where we go,
>>> And help us to be wise,
>>> In times we need to know.
>>> Let this be our prayer
>>> As we are on our way.
>>> …
>>> We ask that life be kind,
>>> Verdict be ears but blind.
>>> …
>>> La forza che ci dà
>>> …
>>>
Regarding the more combinatorial questions in the list: The problem with Frankl’s conjecture is that we are not aware of connections with other areas and techniques of extremal combinatorics. We know very little on union -close families in general. Also the lonely runner problem looks rather “isolated.” (So from this persepective the problems are not “ripe.” ) Of course, for both these problems a solution (or even an easy solution) could well be a negative solution.
I hope it’s not off-topic to congratulate Gil Kalai for joining Tim Gowers, Terry Tao, Ben Green, Julia Wolf, and many other combinatoric luminaries as editors of the newly launched arXiv overlay journal Discrete Analysis.
May all the manuscripts received by Discrete Analysis be elegantly easy proofs of open problems!
Could you please state the precise formulation of whether polynomials mod 6 can compute MAJORITY? Is this a poly over reals? what can size of coefficients be and what can degree be as a function of number of variables in MAJORITY?
>>>
>>>
Ora, destino dei enigmi . . .
>>>
>>>
Nessun dorma! Nessun dorma!
>>>
. . .
>>>
>>>
Dilegua, o notte!
>>>
Tramontate, stelle!
>>>
Tramontate, stelle!
>>>
All’alba vincerò!
>>>
Vincerò! Vincerò!
>>>
Proof of P ≠ NP
****
\begin{equation*}
\begin{aligned}
L & = \{ D \, | \, permuted \, C \, on \, its \, submatrices \, C_{i} \, \}
\ \\
\ \\
C & = [\,C_{1}\, C_{2}\, …\, C_{k-1} \, C_{k} \, C_{k+1} \, … \, C_{2k-1}\, C_{2k} ]
\ \\
\ \\
C_{i} & =
\begin{bmatrix}
\begin{aligned}
&C_{1,i}\\ \\
&C_{2,i}\\ \\
&…\\ \\
&C_{l,i}
\end{aligned}
\end{bmatrix}
=
\begin{bmatrix}
c_{1,j+1} & c_{1,j+2} & \dots & c_{1,j+16}\\ \\
c_{2,j+1} & c_{2,j+2} & \dots & c_{2,j+16}\\ \\
…\\ \\
c_{l,j+1} & c_{l,j+2} & \dots & c_{l,j+16}
\end{bmatrix}
\end{aligned}
\end{equation*}
\ \\
\begin{flushleft}
where $j = (i-1) \! \times \! 16$ and $c_{i,j} \in \{0, 1\}$
\ \\
\ \\
$1c_{s,1}c_{s,2}\dots c_{s,k}1$ for $1 \le s \le l$ are all primes
\ \\
\ \\
for $l = 100, m = 11, n = 2^{m}, k = n/16$
\end{flushleft}
****
The above is the entire proof for P ≠ NP, and covers, in fact, much more than merely that particular containment result.
(If the Latex segment does not display properly, this Mathoverflow URL should show an available version of it.)
****
For people who find the above exposè too terse, the following is a quite verbose version.
To prove the inequality, the very first thing we need to be aware of is that we only have to find, as one approach, a single NP problem that is of super-polynomial complexity, equivalently per Cook’s Definition. The above language L presents such a problem via its membership question, but we will build another NP language with super-polynomial complexity, step by step, so as to show the idea behind.
— Alice obtains a 4096-bit random number
— and randomly shuffles the bits but records
— the shuffle. She presents the scrambled bit
— string and challenges Bob to tell what the
— original random number is.
— Bob obviously can not do it and asks Alice
— to show the original random number and a
— way to convince him that it is the original.
— Alice shows the recorded shuffle. But she
— can not convince Bob.
This example shows that the shuffle is not revertible, but is not verifiable either. It looks like obvious nonsense, but is exactly what we need. Instead of some NP/NPC problem that we remember backwards and forwards, we start with one that is guaranteed impossible, even though not verifiable, yet.
We notice that the inability to verify is due to full semantics density of random numbers, i.e. any pattern is valid, as random number can be of any pattern.
— Alice repeats with a 4096-bit prime,
— and Bob is still not convinced, but is
— less skeptical, since prime numbers
— are of certain patterns and a number
— of any pattern is not necessarily a prime.
— If Alice does not have the prime, it will be
— some work for her to find out a shuffling
— to make the result a prime.
We notice that verifiability is slightly improved but the situation with convincing Bob is not changed at all.
What can Alice do to further improve? Alice adopts the following.
— She generates a second 4096-bit prime
— and performs the same shuffle on both
— primes. Bob is much less skeptical now,
— since for the shuffled results to be
— shuffled back to primes simultaneously
— is much less likely unless Alice really
— knows the original primes.
We do not have to know prime distribution to know that there must be a number k that virtually guarantees the uniqueness of the shuffle for k 4096-bit strings to be simultaneously prime. With the certificate, i.e. the recorded shuffle, Alice can surely convince Bob. In other words, the scrambled results are verifiable to be from the original primes and the complexity of reverting the shuffle, in the absence of its knowledge, is exponential, or more precisely factorial. Of course, k is not a rigid threshold. (I would like to point out that we are not going to deal with the interesting issue of verifiability and uniqueness as a combined entity, in case you have sensed it, as it is beyond the scope of “P vs. NP”.)
Referring back to L, it is obvious that, if the construction is understood, the language itself is proof for P ≠ NP, since it is an NP language (verifiable with certificate) of super-polynomial complexity.
Also obvious is that language L is of elementary mathematics and is short enough to fit in the top margin of a page in any normal textbook. But we should realize that it is not just the proof for P ≠ NP. It actually is also the proof for the other two of the Trio. Since NP is fully exponential, and coNP problems can also be solved in exponential time, so NP = coNP trivially. The third conjecture is also a no-brainer.
We can not fail to realize that L is a P language, or rather, a language of constant complexity, due to l and m being fixed. So, we have in fact proved P ≠ NP with a P language! This highlights that many considerations about the asymptotic behavior are largely a waste of time. If it is super-polynomial, it is super-polynomial. The growth in problem size can hardly be a significant factor. Besides, “All instances of an NP-complete problem are difficult is wrong” is wrong. Any formulation for average complexity may have little to offer and any attempt at some meaningful formulation of it may forever be futile.
Other things, though implied, are quite obvious, such as the existence of one way (invertible) function, but not relevant to the scope of “P vs. NP”, which only concerns one way verifiability.
— Roielle Hugh
>>>
>>>
Now, fate of the riddles . . .
>>>
>>>
None shall sleep! None shall sleep!
>>>
. . .
>>>
>>>
Stars, fade! And night, retire!
>>>
Daybreak, join in the choir!
>>>
O twilight! Victory!
>>>
Victory! Victory!
>>>
A problem could be easy if a competent mathematician could solve it, given a short but non-obvious hint.
One way to attempt such problems in parallel, given a large number of mathematicians, would be supply each such mathematician with a randomly chosen hint, for instance by sampling at random from a textbook. This would be one way of making use of a large number of ?hobbyist? mathematicians.
(see also https://en.wikipedia.org/wiki/Bibliomancy)
Awesome. I love hearing about open problems that seem easy. I was delighted to see that you included two problems on finite automata! 🙂
PUC Logic Failed?
Dick and Ken,
I believe I said ‘coming Monday’, which was September 7, right?
Which year are we in? 1752?
I did deliver. It is character assassination to create the impression that I am a liar. Not quite nice. 🙂
By PUC logic, if the proof fails in any way, it must succeed. Or should I request charity for sanity? 🙂
If there is anything unclear or any error, we should clarify and expose. But without that PUC logical piece about “P vs. NP” for everybody to see, I am incapable of twisting logic to have it on exhibit.
Withholding a piece of history is not the right way to write history. 🙂 So, please, kindly allow me to do it a second time.
Thanks!
****
>>>
>>> Ora, destino dei enigmi . . .
>>>
>>> Nessun dorma! Nessun dorma!
>>> . . .
>>>
>>> Dilegua, o notte!
>>> Tramontate, stelle!
>>> Tramontate, stelle!
>>> All’alba vincerò!
>>> Vincerò! Vincerò!
>>>
Proof of P ≠ NP
\begin{equation*}
\begin{aligned}
L & = \{ D \, | \, permuted \, C \, on \, its \, submatrices \, C_{i} \, \}
\ \\
\ \\
C & = [\,C_{1}\, C_{2}\, …\, C_{k-1} \, C_{k} \, C_{k+1} \, … \, C_{2k-1}\, C_{2k} ]
\ \\
\ \\
C_{i} & =
\begin{bmatrix}
\begin{aligned}
&C_{1,i}\\ \\
&C_{2,i}\\ \\
&…\\ \\
&C_{l,i}
\end{aligned}
\end{bmatrix}
=
\begin{bmatrix}
c_{1,j+1} & c_{1,j+2} & \dots & c_{1,j+16}\\ \\
c_{2,j+1} & c_{2,j+2} & \dots & c_{2,j+16}\\ \\
…\\ \\
c_{l,j+1} & c_{l,j+2} & \dots & c_{l,j+16}
\end{bmatrix}
\end{aligned}
\end{equation*}
\ \\
\begin{flushleft}
where $j = (i-1) \! \times \! 16$ and $c_{i,j} \in \{0, 1\}$
\ \\
\ \\
$1c_{s,1}c_{s,2}\dots c_{s,k}1$ for $1 \le s \le l$ are all primes
\ \\
\ \\
for $l = 100, m = 11, n = 2^{m}, k = n/16$
\end{flushleft}
The above is the entire proof for P ≠ NP, and covers, in fact, much more than merely that particular containment result.
(If the Latex segment does not display properly, this Mathoverflow URL should show an available version of it.)
****
For people who find the above exposè too terse, the following is a quite verbose version.
To prove the inequality, the very first thing we need to be aware of is that we only have to find, as one approach, a single NP problem that is of super-polynomial complexity, equivalently per Cook’s Definition. The above language L presents such a problem via its membership question, but we will build another NP language with super-polynomial complexity, step by step, so as to show the idea behind.
— Alice obtains a 4096-bit random number
— and randomly shuffles the bits but records
— the shuffle. She presents the scrambled bit
— string and challenges Bob to tell what the
— original random number is.
— Bob obviously can not do it and asks Alice
— to show the original random number and a
— way to convince him that it is the original.
— Alice shows the recorded shuffle. But she
— can not convince Bob.
This example shows that the shuffle is not revertible, but is not verifiable either. It looks like obvious nonsense, but is exactly what we need. Instead of some NP/NPC problem that we remember backwards and forwards, we start with one that is guaranteed impossible, even though not verifiable, yet.
We notice that the inability to verify is due to full semantics density of random numbers, i.e. any pattern is valid, as random number can be of any pattern.
— Alice repeats with a 4096-bit prime,
— and Bob is still not convinced, but is
— less skeptical, since prime numbers
— are of certain patterns and a number
— of any pattern is not necessarily a prime.
— If Alice does not have the prime, it will be
— some work for her to find out a shuffling
— to make the result a prime.
We notice that verifiability is slightly improved but the situation with convincing Bob is not changed at all.
What can Alice do to further improve? Alice adopts the following.
— She generates a second 4096-bit prime
— and performs the same shuffle on both
— primes. Bob is much less skeptical now,
— since for the shuffled results to be
— shuffled back to primes simultaneously
— is much less likely unless Alice really
— knows the original primes.
We do not have to know prime distribution to know that there must be a number k that virtually guarantees the uniqueness of the shuffle for k 4096-bit strings to be simultaneously prime. With the certificate, i.e. the recorded shuffle, Alice can surely convince Bob. In other words, the scrambled results are verifiable to be from the original primes and the complexity of reverting the shuffle, in the absence of its knowledge, is exponential, or more precisely factorial. Of course, k is not a rigid threshold. (I would like to point out that we are not going to deal with the interesting issue of verifiability and uniqueness as a combined entity, in case you have sensed it, as it is beyond the scope of “P vs. NP”.)
Referring back to L, it is obvious that, if the construction is understood, the language itself is proof for P ≠ NP, since it is an NP language (verifiable with certificate) of super-polynomial complexity.
Also obvious is that language L is of elementary mathematics and is short enough to fit in the top margin of a page in any normal textbook. But we should realize that it is not just the proof for P ≠ NP. It actually is also the proof for the other two of the Trio. Since NP is fully exponential, and coNP problems can also be solved in exponential time, so NP = coNP trivially. The third conjecture is also a no-brainer.
We can not fail to realize that L is a P language, or rather, a language of constant complexity, due to l and m being fixed. So, we have in fact proved P ≠ NP with a P language! This highlights that many considerations about the asymptotic behavior are largely a waste of time. If it is super-polynomial, it is super-polynomial. The growth in problem size can hardly be a significant factor. Besides, “All instances of an NP-complete problem are difficult is wrong” is wrong. Any formulation for average complexity may have little to offer and any attempt at some meaningful formulation of it may forever be futile.
Other things, though implied, are quite obvious, such as the existence of one way (invertible) function, but not relevant to the scope of “P vs. NP”, which only concerns one way verifiability.
— Roielle Hugh
>>>
>>> Now, fate of the riddles . . .
>>>
>>> None shall sleep! None shall sleep!
>>> . . .
>>>
>>> Stars, fade! And night, retire!
>>> Daybreak, join in the choir!
>>>
O twilight! Victory!
>>>
Victory! Victory!
>>>
Hi,
I believe I have proved that NP = PSPACE finding a problem in NP that it is also in PSPACE-complete. I have submitted to a journal and I have received the following answer:
(Unfortunately we have judged not to accept your note.
We believe that the result is erroneous.
In general , when one claims an equality of P , or NP and PSPACE , one must first convince some known experts individually and put the proof in the web before submitting.
Many journals receive many wrong proofs with respect to the above. Many reviewers simply deny to look at such claims , if the above conditions are not met…)
In despite of that decision, I believe my proof is correct. I shared the paper in a preprint:
https://hal.archives-ouvertes.fr/hal-01196489
Could you give your opinion about it, please?
Regards,
Frank.
https://math.stackexchange.com/questions/3301706/hausdorff-space-homeomorphism-and-collatz-conjecture