Can we get a solution out in one question by asking it to provide a solution, along with a proof that that is the shortest statement of a solution? Then the filter checks the proof, and prints the solution iff it is valid. (Without printing the proof of minimality.)
The issue is that we would like to assume that the genie is smart (think AGI) but not omniscient. I expect that if a hundred smart humans worked for a hundred years they could prove the Riemann hypothesis. I very much doubt that they could prove they had found the shortest proof (in fact in general, statements like that can undecidable quickly). In fact, I very much doubt they could even find the shortest proof at all. All I’m looking for is the shortest proof the AI can manage to find (which is why it is extremely subtle to formalize what I mean by “the AI has no influence”).
Fair enough. In my defense, I don’t think that we have done as much good as 100 smart people working collaboratively and continuously for 100 years would do—not even close. But even if we have done only 10% of that, our failure still bodes badly for my assertion.
As a non mathematician I am genuinely curious as to what we could do with a proof of the hypothesis that we could not do by merely assuming it. Since some consider it the most important problem in pure mathematics it must be something.
It has a bearing on encryption of course (given the relevance to prime numbers) however the proof would only make the encryption weaker so assuming it gives no vulnerability. It would seem from a naive viewpoint that more than the proof itself some of the intermediate steps required to construct the proof may be of greater potential value.
As is usual in mathematics, a proof of the Riemann hypothesis would almost certainly do more than just tell us that it’s true- in order to prove something like that, you usually need to get a handle on deeper and more general structures.
For instance, Wiles’ proof of Fermat’s Last Theorem made massive progress on the modularity conjecture, which was then proved in full a few years later. Similarly, the proof of the Poincare conjecture consisted of a great and general advance in the “surgery” of singularities in the Ricci flow.
To think of an easier example, solving general cubic equations over the integers led mathematicians to complex numbers (it was easy to ignore complex solutions in the quadratic case, but in the cubic case you sometimes need to do complex arithmetic just to calculate the real root), and higher-order polynomial solutions led to Galois theory and more.
I once caught a nice popular talk by John H. Conway, about the sorts of extra things we would expect to learn from a proof of the Riemann Hypothesis.
The issue is that we would like to assume that the genie is smart (think AGI) but not omniscient. I expect that if a hundred smart humans worked for a hundred years they could prove the Riemann hypothesis. I very much doubt that they could prove they had found the shortest proof.
Agreed
(in fact in general, statements like that can undecidable quickly)
Surely “check all the proofs in order” is an algorithmic way to determine that a given proof is the shortest?
All I’m looking for is the shortest proof the AI can manage to find (which is why it is extremely subtle to formalize what I mean by “the AI has no influence”).
Then we agree with each other, but you might want to edit your post to reflect this. Asking “is there a proof of length 2?” seems to indicate my interpretation rather than “can you find a proof of length 2?”.
“Finding the shortest proof” given that you already have one is decidable.
If you have a proof of n characters, and your character alphabet has b symbols, then you just have to enumerate and check all the finitely many strings of length 1 (b^1 of them), length 2, (b^2 of them), …, and of length n-1 (b^(n-1) of them), for proof-ness. If none of those are a proof, then your length n proof is the shortest. Otherwise, the shortest one you found is :)
By “proof” I mean a proof of the statement in question; there are several obvious tweaks to the enumeration process (stopping early, only generating strings that end in QED, generating only syntactically well formed strings, etc), but of course it’s still completely impractical if you’re going to have to enumerate more than 2^70 or so.
Of course you’re both right. In my defense, there is a strong theoretical connection between undecidability and not being in P.
In general, there is probably no reasonably short proof, that an arbiter would have time to verify, that a purported proof of the Riemann hypothesis is the shortest. This is independent of how smart the genie is.
there is probably no reasonably short proof, that an arbiter would have time to verify, that a purported proof of the Riemann hypothesis is the shortest.
Agree (“probably”). Would be interesting if there were a proof from complexity theory or elsewhere that it’s expensive to compute in some sense. That we can’t imagine a method is different from a proof that there can’t be one (for proving some general class of “hard to prove/disprove” statements like RH; obviously there’s a constant answer to “shortest proof of a fixed claim”).
If you replace Riemann hypothesis by “any provable mathematical statement” and you allow arbitrary verification procedures instead of just the normal mathematical ones, then the question is probably equivalent to P = coNP, which is equivalent to P = NP.
I assume you’re thinking of this—P=coNP ⇒ polytime decision for propositional tautologies (but not for mixed quanitifier bool. formulas). It’s CoNP-complete to decide tautologies (implicit forall for all the prop. vars) and NP-complete to decide satisfiability (implicit exists for all the prop. vars).
I don’t understand what you mean by “arbitrary verification procedures”—maybe you’re talking about a different result than the one I linked above?
Can we get a solution out in one question by asking it to provide a solution, along with a proof that that is the shortest statement of a solution? Then the filter checks the proof, and prints the solution iff it is valid. (Without printing the proof of minimality.)
The issue is that we would like to assume that the genie is smart (think AGI) but not omniscient. I expect that if a hundred smart humans worked for a hundred years they could prove the Riemann hypothesis. I very much doubt that they could prove they had found the shortest proof (in fact in general, statements like that can undecidable quickly). In fact, I very much doubt they could even find the shortest proof at all. All I’m looking for is the shortest proof the AI can manage to find (which is why it is extremely subtle to formalize what I mean by “the AI has no influence”).
Incidentally, the Riemann hypothesis was first proposed in 1859, more than one hundred years ago.
Fair enough. In my defense, I don’t think that we have done as much good as 100 smart people working collaboratively and continuously for 100 years would do—not even close. But even if we have done only 10% of that, our failure still bodes badly for my assertion.
As a non mathematician I am genuinely curious as to what we could do with a proof of the hypothesis that we could not do by merely assuming it. Since some consider it the most important problem in pure mathematics it must be something.
It has a bearing on encryption of course (given the relevance to prime numbers) however the proof would only make the encryption weaker so assuming it gives no vulnerability. It would seem from a naive viewpoint that more than the proof itself some of the intermediate steps required to construct the proof may be of greater potential value.
As is usual in mathematics, a proof of the Riemann hypothesis would almost certainly do more than just tell us that it’s true- in order to prove something like that, you usually need to get a handle on deeper and more general structures.
For instance, Wiles’ proof of Fermat’s Last Theorem made massive progress on the modularity conjecture, which was then proved in full a few years later. Similarly, the proof of the Poincare conjecture consisted of a great and general advance in the “surgery” of singularities in the Ricci flow.
To think of an easier example, solving general cubic equations over the integers led mathematicians to complex numbers (it was easy to ignore complex solutions in the quadratic case, but in the cubic case you sometimes need to do complex arithmetic just to calculate the real root), and higher-order polynomial solutions led to Galois theory and more.
I once caught a nice popular talk by John H. Conway, about the sorts of extra things we would expect to learn from a proof of the Riemann Hypothesis.
Agreed
Surely “check all the proofs in order” is an algorithmic way to determine that a given proof is the shortest?
Then we agree with each other, but you might want to edit your post to reflect this. Asking “is there a proof of length 2?” seems to indicate my interpretation rather than “can you find a proof of length 2?”.
“Finding the shortest proof” given that you already have one is decidable.
If you have a proof of n characters, and your character alphabet has b symbols, then you just have to enumerate and check all the finitely many strings of length 1 (b^1 of them), length 2, (b^2 of them), …, and of length n-1 (b^(n-1) of them), for proof-ness. If none of those are a proof, then your length n proof is the shortest. Otherwise, the shortest one you found is :)
By “proof” I mean a proof of the statement in question; there are several obvious tweaks to the enumeration process (stopping early, only generating strings that end in QED, generating only syntactically well formed strings, etc), but of course it’s still completely impractical if you’re going to have to enumerate more than 2^70 or so.
Of course you’re both right. In my defense, there is a strong theoretical connection between undecidability and not being in P.
In general, there is probably no reasonably short proof, that an arbiter would have time to verify, that a purported proof of the Riemann hypothesis is the shortest. This is independent of how smart the genie is.
Agree (“probably”). Would be interesting if there were a proof from complexity theory or elsewhere that it’s expensive to compute in some sense. That we can’t imagine a method is different from a proof that there can’t be one (for proving some general class of “hard to prove/disprove” statements like RH; obviously there’s a constant answer to “shortest proof of a fixed claim”).
If you replace Riemann hypothesis by “any provable mathematical statement” and you allow arbitrary verification procedures instead of just the normal mathematical ones, then the question is probably equivalent to P = coNP, which is equivalent to P = NP.
I assume you’re thinking of this—P=coNP ⇒ polytime decision for propositional tautologies (but not for mixed quanitifier bool. formulas). It’s CoNP-complete to decide tautologies (implicit forall for all the prop. vars) and NP-complete to decide satisfiability (implicit exists for all the prop. vars).
I don’t understand what you mean by “arbitrary verification procedures”—maybe you’re talking about a different result than the one I linked above?
Right—those are equivalent.