And it’s not even the *only* non-paradoxical answer! The genie could just pick some question that takes more than 200 characters to specify, and answer it—that doesn’t imply that *you yourself* could have specified the same question using fewer than 200 characters. To force the answer “No such question exists,” you really want something like: “what is the *lexicographically first* NP question that can’t be asked in fewer than 200 characters, and its answer, and a proof of the answer, and a proof that nothing yielding the same answer can be asked in fewer than 200 characters and that the question is lexicographically first?”

“What is an NP question that cannot be asked in less than 200 characters, and what is the answer to that question?”

The genie’s response itself allows the questioner to easily verify (by definition) that the question in the genie’s response cannot be asked in less than 200 characters, even though there is no understanding/verification of the question at the lower level… but then you run into Jerry’s Paradox because we somehow got the answer within the answer using less than 200 characters.

I think this kind of NP genie is really an oracle in disguise.

]]>So I think the genie has to take two arguments, the question and the current state of the art, and replies with a certificate the questioner can understand, if possible. This makes a “no” answer much less useful, since it means either no certificate exists, or a certificate exists but you won’t understand it. The genie cannot resolve this for you, since then it is not an NP genie but one of a more general and much more powerful kind.

]]>I would rather ask about evidence of the development of Greek mathematics. That truly is something hugely important for world civilization. Finding about more of pre-Euclid mathematics would be great, for example, or indeed about Euclid himself.

]]>Christianity promises resurrection, which is regarded with favor. ]]>

We can still repair that a bit: “What’s the most important named conjecture which is undecidable in ZFC and its undecidability in ZFC is provable in ZFC + a large cardinal axiom for some large cardinal axiom that is in the literature.” More work on defining “important” might be necessary.

]]>