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:

- "The Riemann Hypothesis is true" …
*a $\Pi^0_1$ counterexample could exist*;

(per Noam Elkies' comment) - "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); - "$\mathsf{P}\ne\mathsf{NP}$" …
*no obvious $\Pi^0_1$ counterexample*

(per Bjørn Kjos-Hanssen's answer); - "Navier–Stokes is globally regular" …
*no obvious $\Pi^0_1$ counterexample*

(per Terry Tao's answer); - "Yang–Mills has a mass gap" …
*no obvious $\Pi^0_1$ counterexample (?)*; - "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.

14more comments