38

Three good answers were received — by Alex Gavrilov, Bjørn Kjos-Hanssen, and Terry Tao — and the bounty has been awarded (somewhat arbitrarily) to Alex Gavrilov.

The answers are summarized below; because they are open-ended and technically subtle, the question has been flagged for conversion to community Wiki.

Thanks are extended to all who contributed.

Summary  Harry Altman cogently commented:

This is essentially asking which of these statements are equivalent to a $\Pi^0_1$ statement, right?

We embed this insight into a better version of the question:

Which of the Millennium Prize problems can be stated as a postulate that can be falsified by a $\Pi^0_1$ counterexample?

to which the answers given (as I understand them) amount to:

  1. "The Riemann Hypothesis is true" …a $\Pi^0_1$ counterexample could exist;
    (per Noam Elkies' comment)
  2. "The Birch and Swinnerton-Dyer Conjecture is true" … conceivably a $\Pi^0_1$ counterexample could be constructed, but not with present knowledge (per Alex Gavrilov's answer);
  3. "$\mathsf{P}\ne\mathsf{NP}$" … no obvious $\Pi^0_1$ counterexample
    (per Bjørn Kjos-Hanssen's answer);
  4. "Navier–Stokes is globally regular" … no obvious $\Pi^0_1$ counterexample
    (per Terry Tao's answer);
  5. "Yang–Mills has a mass gap" … no obvious $\Pi^0_1$ counterexample (?);
  6. "The Hodge Conjecture is true" … no obvious $\Pi^0_1$ counterexample (?);

Resource  Wikipedia's article Arithmetical Hierarchy explains the notation of Harry Altman's answer.

What "No Obvious $\Pi^0_1$ Counterexample" Means   As was noted on Dick Lipton and Ken Regan's weblog Gödel's Lost Letter and P=NP, the authority of the Scientific Advisory Board (SAB) of the Clay Mathematics Institute (CMI) extends to:

"The SAB may consider recommending the award of the prize to an individual who has published work that, in the judgement of the SAB, fully resolves the questions raised by one of the Millennium Prize Problems even if it does not exactly meet the wording in the official problem description.”

In view of the CMI/SAB's supreme executive authority, the logical possibility of amending a Millennium Prize question to accommodate $\Pi^0_1$ counterexamples — via ingenious "burning arrows," to adopt Dick Lipton and Ken Regan's phrase — cannot be formally excluded.

Community
  • 1
John Sidles
  • 1,359
  • 1
    I don't understand the RH argument. Complex numbers can be arbitrarily complicated (as Chaitin himself should know best!). One can easily find a sequence that is Cauchy if and only if your favorite Turing machine halts. – darij grinberg Sep 30 '12 at 02:17
  • 2
    @darij: This is the point of http://mathoverflow.net/questions/31846/is-the-riemann-hypothesis-equivalent-to-a-pi-1-sentence/ – Andrés E. Caicedo Sep 30 '12 at 02:51
  • 16
    The point is that if there's a counterexample then one can prove it by a contour integral: no need to actually locate the zero, only to prove there's one in a circle disjoint from the critical line. – Noam D. Elkies Sep 30 '12 at 03:03
  • 2
    What if a different model of set theory contained an extra complex number that violated the Riemann Hypothesis? Or a nonstandard natural number violating one of the equivalent finitary statements? Would you still consider the Riemann Hypothesis to be a "true" statement? – zeb Sep 30 '12 at 03:11
  • 3
    @zeb: "True" means "true in the standard model". – Andrés E. Caicedo Sep 30 '12 at 03:19
  • 10
    So if I understand correctly, this is essentially asking which of these statements are equivalent to a $\Pi_1^0$ statement, right? – Harry Altman Sep 30 '12 at 04:01
  • 2
    If an elliptic curve has rank at least $n$ we can always write down $n$ rational solutions. If the $L$-function has a zero of order less than $n$ at $s=1$ then we can determine this by accurately approximating a contour integral in sufficiently small loop around $s=1$, which I think is always possible. If this works then undecidability of BSD implies that the analytic rank is greater than the algebraic rank. The other inequality appears more elusive. – Will Sawin Sep 30 '12 at 05:59
  • 2
    Like the Riemann Hypothesis, the Poincar'e Conjecture (which is, of course, now known to be true) also had the property that there is an algorithm to find a counterexample. Rubinstein described an algorithm that determines whether or not a 3-manifold is the 3-sphere. On the other hand, a naive procedure will eventually confirm if any CW-complex is simply connected. – HJRW Sep 30 '12 at 06:25
  • 2
    @HW: Isn't computing whether a CW-complex is simply-connected an undecidable problem? – Will Sawin Sep 30 '12 at 06:48
  • 5
    Will - yes, but the undecidable bit is to prove that a CW-complex is not simply connected. There is a partial algorithm that terminates if and only if an input CW-complex is simply connected or, equivalently, an group presentation presents the trivial group, and this is enough for these purposes. The partial algorithm simply tries to write each generator as a product of conjugates of relators. – HJRW Sep 30 '12 at 06:54
  • 2
    It is undecidable whether a 2-complex is simply connected, but it is decidable whether a 3-manifold is simply connected. (This should not be shocking to someone who know how to make a 4-manifold with arbitrary fundamental group.) – Ben Wieland Sep 30 '12 at 19:03
  • 2
    This reminds me the situation with the continuum hypothesis (CH), which is known to be undecidable in ZFC theory. There is statement that under CH, there exists an entire holomorphic function with some property P about its zero; and the opposite, under the negation of CH, there does not exist such a function. I apologize for having forgotten what is P. – Denis Serre Sep 30 '12 at 19:39
  • 2
    Ben - yes, but the proof that one can decide if a 3-manifold is simply connected relies on the Poincare Conjecture! So that reasoning is circular. – HJRW Sep 30 '12 at 19:53
  • 2
    @Denis: You might be thinking of a result from Erdos that I learned in proofs from THE BOOK: suppose $\lbrace f_\alpha \rbrace$ is a family of holomorphic functions such that when you evaluate the family at some fixed $z\in \mathbb{C}$, you can only get countably many values. Then, $\neg CH$ implies that such a family must itself be countable, but there are such families of continuum size if $CH$ holds. There is a link to the original paper in this MO answer: http://mathoverflow.net/questions/1924/what-are-some-reasonable-sounding-statements-that-are-independent-of-zfc/1958#1958 – Thierry Zell Sep 30 '12 at 21:12
  • 1
    Somewhat related: NP captures something about the nature of a proof: proofs are (in general) hard to find but (by definition) easy to check. Therefore, if $P\neq NP$, proving this might be very hard (or even infeasible). If, on the other hand, $P=NP$, a proof should be much easier to find. – Ansgar Esztermann Apr 11 '14 at 13:21
  • @Ansgar, one counterintuitive obstruction (of many) that makes the assertion P=NP surprisingly difficult to verify, even if it's true, is the formal possibility --- which is excluded neither by existing mathematical knowledge nor by the Clay Institute problem statement for PvsNP --- that P=NP for languages whose membership in P is affirmed by an oracle yet not decidable in ZFC. The TCS Stackexchange community wiki "Does P contain languages whose existence is independent of PA or ZFC?" surveys these considerations. Oracles are tricky! – John Sidles Apr 11 '14 at 13:48
  • 1
    You're talking about the Millennium problems, and you are offering only a 100pt bounty? I guess, when it is only a single "n" instead of "nn" then the prize is lower. – Włodzimierz Holsztyński Apr 11 '14 at 16:52
  • On Dick Lipton and Ken Regan's weblog Godel's Lost Letter and P=NP, I have posted a comment that summarizes the CMI's Millennium Prize criteria, together with a link to Dick and Ken's favorite Far Side cartoon: "The One Where They're Lighting Their Arrows". – John Sidles Apr 14 '14 at 09:49
  • Made CW at OP's request. – Todd Trimble Apr 18 '14 at 00:43

3 Answers3

21

$P\ne NP$ is a $\Pi^0_2$ statement:

for each polynomial $p$ and Turing machine $M$ implementing an algorithm attempting to decide SAT, there is a formula $\phi_M$ such that if we look at the computation of $M$ on input $\phi_M$ after $p(|\phi_M|)$ computation steps, $M$ has either not halted or it has answered incorrectly.

(Edit: added more detail to the $\Pi^0_2$ statement above.)

If we place a computable bound on the size of $\phi_M$ as a function of $M$ then we can improve this to a $\Pi^0_1$ statement, and hence will have the property $\text{undecidable}\rightarrow\text{true}$, since true $\Sigma^0_1$ statements are provable (in Peano Arithmetic). Of course in a formal sense, any provable statement is equivalent to $0=0$ which is $\Pi^0_1$.

Is it plausible that that $P\ne NP$, but there is no computable bound on $|\phi_M|$? This would mean that there are algorithms that do "arbitrarily well" at solving SAT in polynomial time. That is, relative to their description, they are correct for an Ackermann-function or busy-beaver-function level many $\phi$'s.

But intuitively, there is not much structure in SAT to exploit, and so once you have so many variables $x_1,\ldots,x_v$ that a random assignment of truth values has higher Kolmogorov complexity than $M$: $$K(M)\le v + O(1) $$ then there ought to be a $\phi(x_1,\ldots,x_m)$ on which $M$ fails. Since $K(M)$ has a computable bound as a function of $M$, it would follow that $M\mapsto |\phi_M|$ is computably bounded. This is probably off by a "factor" somewhere; maybe a better way is to say that $P^A\ne NP^A$ for a random oracle $A$, and in that case $\phi_M$ is computably bounded.

So we can make a plausible "computably bounded $P\ne NP$ conjecture" that $M\mapsto \phi_M$ is computably bounded (with a specific bound being incorporated into the conjecture), which does have the property $\text{undecidable}\rightarrow\text{true}$.

Bjørn Kjos-Hanssen
  • 24,629
  • 2
    Bjorn, your bound-restriction nicely addressed Scott Aaronson's weblog remark "Independence from ZFC is not a property of the language L itself, but only a property of how I described L to you! … something like 'the subclass of P consisting of all languages that ZFC can prove are in P' doesn’t even make sense" (an objection that a TCS StackExchange wiki addressed too). Restrictions can be tricky, and so I'll reflect further on your fine answer in the next few days. – John Sidles Apr 12 '14 at 09:31
  • Bjorn, in regard to "true $\Sigma^0_1$ statements are provable in PA", and specifically in regard to the exemplar "$M\in\text{P}$ and fails for no formula length-bounded by $\phi_M$", is the latter really in $\Sigma^0_1$? Isn't "$M\in\text{P}$" itself undecidable in PA (and even in all formal systems)? Your answer's overall strategy of "improving" $\text{P}\ne\text{NP}$ to a $\Pi^0_1$ statement is promising, but perhaps the "$M\in\text{P}$" element of it requires adjustment? – John Sidles Apr 14 '14 at 09:07
  • Thank you very much, Bjørn. I greatly appreciate your efforts (as do your many MathOverflow up-raters), and look forward to "details". What Felix Klein said of curves, perhaps applies also to $M\in\text{P}$: "Everyone knows what a curve is [what $M\in\text{P}$ means], until (s)he has studied enough mathematics to become confused through the countless number of possible exceptions." – John Sidles Apr 14 '14 at 10:50
  • The (seemingly) tricky consideration is that a decision-$M\in\text{P}$ can require (for example) $c+n^3$ operations (where $c$ is some integer)... yet because $c$ is unbounded, this restriction provides no concrete criteria for stopping an $M$-simulation. These objections can be overcome, but some well-considered modifications/restrictions to the membership criteria for $P$ are needed (possibly of Juris Hartmanis-type?). – John Sidles Apr 14 '14 at 16:52
  • 1
    There is no need to decide whether $M$ runs in polynomial time (which I assume is what you mean by "$M\in P$"); I have put the added detail into an edited version of my answer – Bjørn Kjos-Hanssen Apr 14 '14 at 18:19
  • 1
    Thank you Bjorn. Your construction (as it seems to me) definitely establishes $\text{P}\ne\text{NP}$ as a $\Pi^0_2$ statement. Per recent "burning arrow" comments on Gödel’s Lost Letter, and along the lines of the second half of your answer, it is natural to wonder whether (in your view) there exists any restriction of $\text{P}\ne\text{NP}$ that reduces it to $\Pi^0_1$, while respecting sufficiently the spirit of the problem to "reasonably resolve it" (per the concluding phrase of the Millenium Prize rules)? – John Sidles Apr 14 '14 at 20:08
  • 1
    Well, if there was a short and simple algorithm running very fast, that provably was correct on all $\phi$ of length at most $2^{2^{2^{1000000}}}$, I guess they would consider awarding the prize... – Bjørn Kjos-Hanssen Apr 14 '14 at 20:25
  • Bjørn Kjos-Hanssen, you deserve a bounty, for taking the time to give such a well-considered answer (from which I have quoted). Thank you. – John Sidles Apr 18 '14 at 00:26
  • As Harvey Friedman likes to emphasize, Bjørn Kjos-Hanssen's trick of strengthening P≠NP to a $\Pi^0_1$ statement is a very general principle. E.g., for Navier-Stokes, we can strengthen the statement in Tao's answer ("for all $T,E>0$ there exists $M$") by demanding that $M$ be effectively computable. In fact, in practice, when a major conjecture is proved but part of the proof is ineffective, people almost always ask at once whether it can be made effective. So, secretly, the real question people want answered is a $\Pi^0_1$ strengthening even if the "official" conjecture is "merely" $\Pi^0_2$. – Timothy Chow Aug 23 '17 at 04:12
  • $\mathrm{P \ne NP}$ is indeed $\Pi_2$, and this classification is optimal in that it cannot be proved to be $\Sigma_2$ by an argument that relativizes. See https://mathoverflow.net/questions/57345/examples-of-g-delta-sets/57348#comment144034_57348 and https://cstheory.stackexchange.com/a/16644 . – Emil Jeřábek Jan 25 '20 at 14:34
19

Global regularity for Navier-Stokes on the torus is (logically equivalent to) a $\Pi_2^0$ statement; this is essentially an unpublished observation of Bourgain (who made it in the more general context of supercritical equations), which I sketched out in this paper http://arxiv.org/abs/0710.1604 . Basically, Navier-Stokes is equivalent to the assertion that for all $T, E > 0$, there exists an $M$ such that all initial data with $H^1$ norm at most $E$, there exists a solution up to time $T$ whose $H^1$ norm is always bounded by $M$. Now if such a claim is the case, it can be verified (using rigorous perturbation theory) by constructing a sufficient number of approximate solutions to a sufficient number of choices of initial data, and verifying that all of these approximate solutions have norm at most $M/2$ (say) up to time $T$, where "sufficient number" is something explicit that depends on $T, E, M$, and the nature of the approximation can be discretised at an explicit scale that also depends on $T,E,M$. So Navier-Stokes is equivalent to a statement of the form $\forall T,E \exists M: P(T,E,M)$ where $P(T,E,M)$ is something that can be verified in finite time for each $T,E,M$ (which can be taken to be rational numbers). (In fact, for each $E$ there is an explicit time $T = T(E)$ for which one needs to verify $P(T,E,M)$, and beyond which global regularity is easily obtained from the energy dissipation, so the claim even simplifies a little to $\forall E \exists M: P( T(E), E, M)$.)

It looks very difficult to me, however, to make Navier-Stokes equivalent to a $\Pi^0_1$ statement. This would basically amount to being able to describe all possible "blowup scenarios" by a countable set, and to be able to determine whether each such blowup scenario can actually happen in finite time. While some blowup scenarios (particularly "stable", "approximately self-similar" ones) can be described and verified in such a manner, it's not clear whether all of them can.

Terry Tao
  • 108,865
  • 31
  • 432
  • 517
  • 1
    Are there examples of $ E $ where $ M $ can be calculated? – Bjørn Kjos-Hanssen Apr 12 '14 at 17:34
  • 1
    For sufficiently small E, perturbation theory allows one to conclude that M depends linearly on E in the limit as E goes to zero. – Terry Tao Apr 13 '14 at 21:13
  • 1
    Terry Tao, you deserve a bounty, for taking the time to give such a well-considered answer (from which I have quoted). I have flagged the amended question/answer for conversion to Community Wiki; please do not hesitate to amend it as you see fit. And, thank you. – John Sidles Apr 18 '14 at 00:26
  • Here is a version of the Navier Stokes problem due to the physicist Giovanni Gallavotti. Given a divergence free vector field on periodic three space defined by a finite fourier series , at a fixed point in space give an algorithm which describes the solution vector field one second later at that point to any degree of precision with an estimated time for the computation at that precision. Is this version of the problem decidable? Dennis Sullivan – Dennis Sullivan Jan 25 '20 at 14:03
17

As Harry Altman pointed out, for a conjecture undecidable -> true means that it can be formulated as a $\Pi_1^0$ statement. To put it simply, if the conjecture is false, one can prove this by an explicit (finite) calculation. I would leave Yang–Mills and Navier–Stokes to someone more familiar with mathematical physics then I am. The other three conjectures, apparently, aren't $\Pi_1^0$ statements for now.

By the way, the Poincare conjecture wasn't a $\Pi_1^0$ statement before Rubinstein's algorithm was discovered (which determines whether or not a 3-manifold is the 3-sphere, see the comment by HJRW). (Expert guys, fix me here if I am wrong). So, whether or not a particular conjecture is in this calss depends on the awailable knowledge. After all, once a conjecture is proven, it is in $\Pi_1^0$ by definition.

Let me begin with Birch and Swinnerton-Dyer Conjecture. Technically, what you need to get \$1M is to prove or disprove the following (http://www.claymath.org/millenium-problems/birch-and-swinnerton-dyer-conjecture). If $E$ is an elliptic curve over $\mathbb{Q}$, then $r = rank(E(Q))$, called arithmetic rank, is equal to the order $r_*$ of zero of $L(E, s)$ at $s=1$, called analytic rank. This conjecture actually consists of two rather different parts, namely $r\le r_*$ and $r\ge r_*$. The first one is a $\Pi_1^0$ statement. If $r>r_*$ for a particular curve $E$, you can prove it by a direct computation (with some luck). The other half of the conjecture is more tricky, as Will Sawin pointed out. The problem is, there is no known algorithm to compute the group $E(Q)$. (Do not take me wrong: there are some algorithms, and they apparently work. We just don't have a proof that they work.)
Theoretically, it is possible that while $r<r_*$ for some curve $E$, you will never know it because you won't be sure if there are some more generators of $E(Q)$ which you did not find yet. In fact, Manin used this very argument in the opposite direction, and proposed an algorithm of computing the Mordell-Weil group assuming the Birch and Swinnerton-Dyer Conjecture to be true. (See Hindry, Silverman "Diophantine Geometry" for details. To be pedantic, you need a bit more then $r=r_*$ for this.)
So, the inequality $r\ge r_*$ is not a $\Pi_1^0$ statement yet, for the best of my knowledge.

I can't say anything sensible about the Hodge conjecture, except that it definitely does not look like $\Pi_1^0$. In order to disprove it by an explicit example, you need to prove that on a particular variety there is no algebraic cycles with a given cohomology class. Maybe experts know better, but I have never heard about any algorithm for a job like this.

Bjørn Kjos-Hanssen already gave an answer about $P\neq NP$, and I don't have much to add. Except for, as I pointed out in a separate question, How to prove a $\Pi_2$ statement properly?, there is a technical possibility that that problem is decidable, but the "decision" is wrong. (Do not take me seriously, I don't really believe in this.)

Community
  • 1
Alex Gavrilov
  • 6,851
  • 1
    What do you mean by, "After all, once a conjecture is proven, it is in $\Pi^0_1$ by definition"? Logically speaking, a sentence $\sigma$ is not in general equivalent to "there is a proof of $\sigma$," as Goedel shows. – Monroe Eskew Apr 11 '14 at 17:54
  • 3
    Yes, but I mean it is proven and assumed to be true. – Alex Gavrilov Apr 11 '14 at 17:58
  • 1
    I don't see how assuming a statement to be true makes it $\Pi^0_1$. – Monroe Eskew Apr 11 '14 at 19:10
  • 5
    Once it's proven, the sentence is proven to be equivalent to a $\Pi^0_1$ statement, namely $0=0$. When we speak of "a sentence" we probably mean "up to provable equivalence" since the Millennium Problems are only defined up to provable equivalence... – Bjørn Kjos-Hanssen Apr 11 '14 at 20:48
  • Alex Gavrilov, you have received the bounty. Thank you for taking the time to give such a well-considered answer. – John Sidles Apr 18 '14 at 00:24
  • @ChristianRemling: “The truth of a conjecture can’t make a set $\Pi^0_1$ if it wasn't so to start with.” Sure, but the $\Pi^0_1$-ness of a set can be implied by (or even equivalent to) some conjecture. A proof of the conjecture can’t change whether the set is $\Pi^0_1$, but it can tell us whether or not it is. – Peter LeFanu Lumsdaine Apr 19 '14 at 18:43