<p>God could (a) provide a proof that factorization was hard and (b) use the idea of the OP to show us that He can factor large numbers. </p>

<p>(Of course, this doesn't work if you think factorization is easy or it's possible to build quantum computers. But then God could choose a different problem to demonstrate with.)</p>

CC BY-SA 3.0
2014-12-22T03:48:12.117Z
Are you allowing some sort of interaction? Otherwise, I don't see how to accomplish (b).
usul
CC BY-SA 3.0
2014-12-22T04:15:14.453Z
No, I'm not. God (a) sends a proof that some kind of randomized problem is hard. (b) solves the randomized problem for the first ten thousand instances, where the random numbers are given by the bits of $\pi$. Even God shouldn't be able to tailor a problem so that the bits of $\pi$ give easily solvable instances, and where the problem description is short compared to the number of bits of $\pi$ that are used.
Peter Shor 
CC BY-SA 3.0
2014-12-22T14:42:13.657Z
I agree that this would be subjectively convincing, but as the original question points out, such a problem *could* be coincidentally easy for those problems or bits of $\pi$. Maybe it's even likely that among all hard problems there exists one where the first 10,000 such instances are easy. Whereas with interaction it seems we can get a closer-to-formal guarantee that either the oracle knows the random bits we are using, or can solve problems in PSPACE.
usul
CC BY-SA 3.0
2014-12-22T15:16:34.183Z
@usul: I think it's much more likely that an advanced civilization has an undetectable surveillance device that can observe your coin flips than that the bits of $\pi$ are sufficiently non-random that there is a problem with a short description that the bits of $\pi$ can solve that beats the information-theoretic bound that would make it impossible with random bits that an adversary knew ahead of time.
Peter Shor 
CC BY-SA 3.0
2014-12-22T19:09:01.923Z
While He's at it, He can also provide a proof that the digits of $\pi$ are indeed random.
Denis
CC BY-SA 3.0
2014-12-22T22:41:13.270Z
@Denis: why not to prove that all our mathematics is wrong then? Digits of any specific computable number (π or else) aren’t random in any sense of the word (you still need much things to learn), unless our theories are contradictory and we can prove *both* they “are random” and “aren’t random” by logical principle of explosion.
Incnis Mrsi
CC BY-SA 3.0
2014-12-22T23:00:50.133Z
@Peter (related to comments, not body text): use of a computable sequence of input data requires a proof that this particular sequence hasn’t special weakness wrt to problem solved. Ī’d be more convinced with input data constructed of published information of ancient origin (literary texts, star catalogs, weather data…), with presumedly low redundancy (that can be achieved by using hashes at expense of injectivity), than with digits of π or so.
Incnis Mrsi
CC BY-SA 3.0
2014-12-22T23:13:57.577Z
@IncnisMrsi Of course I don't mean random in the computable sense but in the distribution of digits: normality of $\pi$ is an open problem. Try interpreting the answers in a way that makes sense before assuming your interlocutor is wrong. And once again, even if he is wrong, avoid unnecessary comments like "you have much to learn", it is really unpleasant and contrary to the website's policy.
Denis
CC BY-SA 3.0
2014-12-21T22:51:55.307Z
2014-12-21T23:00:44.040Z
2014-12-21T23:00:44.040Z
Peter Shor 
<p>Any given piece of data is finite, so it seems difficult for such data to be evidence of asymptotically good computational abilities. Examples like your list of factorizations seem to be subjective (though in practice probably quite convincing that one can solve the problem).</p>

<p>One note is that for any problem outside of NP, we do not even have the computational resources to read or verify a proof that the oracle provides. So in this sense an oracle more powerful than NP is unable to convince us of this fact by providing data to us.</p>

<p>However, if we are given the ability to query the oracle with inputs of our choice, then intuitively this corresponds to the complexity class <a href="http://en.wikipedia.org/wiki/IP_(complexity)" rel="nofollow">IP</a>, so we should be able to convince ourselves that the oracle can solve problems in PSPACE. Of course this is with the finite-data caveat: We can only ever ask questions up to a certain size input. But then again, we only ever care about answering questions up to a certain size input.</p>

CC BY-SA 3.0
2014-12-16T13:05:30.423Z
Could you clarify please? Do you insist without response to our *challenge* any alleged “god” is unable to quell your doubts about beyond-universe computational abilities?
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T13:17:22.563Z
Just a short remark on an interactive case: for me He would be more credible, if He started the communication with the proof that a PSPACE problem A requires exponential time to solve on average case, for some efficiently samplable distribution D. Then, I would sample from this distr. a bunch of instances of size 2^30 and use IP protocol for him to convine me he knows answer. I'd be convinced enough, even though instance size is finite. Can similar thing be done with one shot massage, assuming some problem in NP is hard on average?
Jarosław Błasiok
CC BY-SA 3.0
2014-12-16T14:15:53.680Z
@IncnisMrsi, I don't insist on anything, but yes, if we model ourselves as polynomial-time Turing Machines, then we can only check proofs of NP statements by definition; we cannot always check harder proofs.
usul
CC BY-SA 3.0
2014-12-16T14:20:07.577Z
Hope @usul sees Ī edited the question providing a “virtual challenge protocol”.
Incnis Mrsi
CC BY-SA 3.0
2014-12-22T00:20:19.423Z
@Jarosław: We know already that permanent (modulo a prime) is as hard in the average case as it is in the worst case, we know an IP protocol for permanent, and we know that permanent is NP-hard.
Peter Shor 
CC BY-SA 3.0
2014-12-16T12:58:10.533Z
2014-12-16T12:58:10.533Z
usul
<p>To account for your additional requirement of a nondeterministic universe, another way to go would be arbitrary precision information about physical constants. For instance the code of a Turing Machine which computes gravitational constant $G$ (in $m^3·kg^{−1}·s^{−2}$) with arbitrary precision.</p>

<p>It would be indeed surprising that such a machine exists, but assume we get one with this guarantee written on it. At the beginning we would just be able to test that the machine matches the current precision on $G$, which is nothing extraordinary. But as technology advances and measurements gets finer and finer, we would be convinced with increasingly high precision that the machine indeed computes $G$.Therefore, assuming scientific progress goes on, we could reach arbitrary precision on the accuracy of the machine, and on the fact that it is "supernatural", because at least as advanced as any level of knowledge we can achieve.</p>

<p>This assumes we are never able to <em>prove</em> that the machine computes $G$, which is based on the assumption that there is no computational link between physical constants (here $G$, and the various constants used to define unities, like the speed of light $c$). This assumption is reasonable in the current state of knowledge, but we never know...</p>

CC BY-SA 3.0
2014-12-16T16:16:52.383Z
OMG… *c* in **metres per second?** Putting aside (dubious) merits of the concept itself, are you serious about **this concrete constant?**
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T16:22:23.543Z
I realized the mistake while you were typing your comment ;) changed it to G
Denis
CC BY-SA 3.0
2014-12-16T16:23:07.930Z
So… which verification procedure do you envisage?
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T16:26:57.000Z
the verification time would depend of the confidence you want (which, again, can never be 100%). At the current speed of progress it is actually quite reasonable: any digit of precision gained on the measure of $G$ divides by ten the probability of failure.
Denis
CC BY-SA 3.0
2014-12-16T16:30:19.797Z
So, any guy able to guess, say, next three digits of *G* (with *a priori* probability about $10^{-3}$) will be deified. Not a good prospect for rationally thinking humans.

By the way, @Denis, are you aware about precision of the currently accepted **definition of kilogram?**
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T16:36:48.650Z
If you are not happy with $10^{-3}$ you can wait longer... The fact that it is a Turing Machine also adds weight to it: once the number of digits correctly guessed greatly exceeds the size of the machine, things cannot be attributed to chance anymore, but there is something weird at work.
Denis
CC BY-SA 3.0
2014-12-16T16:42:28.893Z
about the kilogram yes I know, if you want replace $G$ with Planck time or another one, I'm not a physicist so I didn't choose the optimal constant right away sorry
Denis
CC BY-SA 3.0
2014-12-16T16:48:37.087Z
Also, the concept shows that Denis has very little notion about physical quantities. IMHO a waste of time.
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T16:51:36.843Z
Thank you for your kindness, my last comment was indeed about Kolmogorov complexity, and I now regret having wasted my time trying to give you a satisfying answer. You are basically asking for "what would be an impossible piece of data", and then smugly bash people trying to cope with your expectations. Please read the chart of this website before continuing interacting.
Denis
CC BY-SA 3.0
2014-12-16T16:55:37.430Z
Ī retracted that part of my comment, since (mathematical) nature of dimensionless physical constants is unknown to me to the same degree as to you. But idea to extract practical amounts of information from physical *constants* is risible.
Incnis Mrsi
CC BY-SA 3.0
2014-12-18T17:26:47.853Z
If we'll never actually be able to verify more than around 20 digits of physical constants, what good does knowing hundreds of digits do us?. This will convince us that the message comes from a more advanced civilization, but not God—anything we can verify, an advanced civilization can measure.
Peter Shor 
CC BY-SA 3.0
2014-12-18T19:17:50.217Z
Indeed, the additionnal assumption needed for this to work is that given enough time, humanity will reach any given level of civilization. So asymptotically, it will get convinced (as time tends to infinity) that the message was not from another civilization.
Denis
CC BY-SA 3.0
2014-12-22T15:21:39.487Z
@Denis: There are only a finite (and relatively small) number of digits of any physical constant that can be measured *even if you used the entire space and mass of our galaxy to build a measuring device.* There is no way of distinguishing the prediction of the value of a physical constant from a very, very, lucky guess.
Peter Shor 
CC BY-SA 3.0
2014-12-22T19:04:42.090Z
@PeterShor This is a nice objection. Indeed, if there is a maximum of digits that is reachable by any civilization, then the message could have been sent by such a "maximally advanced" (relatively to this measure) civilization. The idea was to find an objective "measure" of advancement of civilization, such that the "impossible" message would be a machine that can surpass every fixed level if run long enough. Degree of precision on physical constants (i.e. on relations between them) was an imperfect candidate because of the absolute bound you mention, maybe something else can do the job.
Denis
CC BY-SA 3.0
2014-12-16T16:06:13.217Z
2014-12-16T16:30:59.957Z
2014-12-16T16:30:59.957Z
Denis
<p>I am not sure it is in the spirit of your question, but here is a possible lead: a computer which acts as an "all-powerful mathematician", or for that matter, all powerful knowledge in general. This would be a computer with which we can dialogue, and ask it questions like "what is the answer of the Riemann hypothesis". The computer would give the answer and justify it by intuition-level arguments, that can be refined at the will of the questioner, all the way to formal proof if necessary.
Same thing if the results are independent, or if the question does not make sense, the computer would be able to explain it to the questioner in the best possible way for him to get convinced of that.
Any question could be allowed, as "What is the issue with dark matter? Can we design an experiment to settle the question?", and so on...</p>

<p>This interactive device, all-knowing but communcating on a good level for our intuition, would be a good way to violate all that we know about the world. It is able to solve any problem humans can ask themselves, at least any problem for which there is a solution which can be displayed to us in a convincing way, and so in some sense it is the best possible "god-authentification".</p>

<p>This is beyond your (presumable) limitation of a finite piece of data, but we can additionnally respect this condition with this fix:
This device would only work for a finite time, say a year, during which many people (including experts in various fields) could come to question it. During this time, the inside of the machine is sealed and we cannot see the mechanism, it is a blackbox. After "expiration", the lock is opened, and we discover that the answers were hardcoded in the right order, separated by predefined time intervals, and the computer was just reading them. </p>

<p>This is an absolute finite piece of data, that not only "knew" the answers to all the questions we could think of in one year, but additionally "knew" exactly what questions were going to be asked and when. The probability of chance for this can be neglected (such a probability will always exist anyway if the data needs to be finite).</p>

CC BY-SA 3.0
2014-12-16T15:16:48.200Z
Interesting, but the “fix” is impractical. After the black box device is manufactured, it can, generally, succeed only in a tiny subset of all possible futures, namely, where examiners asked only questions with answers provided inside the black box. Or, maybe, Denis expects that God must *influence mind of examiners* to make them ask only right questions?
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T15:22:15.340Z
The "outside of this universe" phenomenon I use here is omniscience (this is only one possible way to go about your question, the other discussions were about computational power which is an equally valid track), which if exists necessarily contradicts free will.
Denis
CC BY-SA 3.0
2014-12-16T15:25:41.180Z
Ī do not believe in uniqueness of future. Yes, your scenario would make me to reconsider my position, and… Ī’d be more astonished by such argument for determinism than by the very fact that God opted to contact the humankind.
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T15:29:11.193Z
Indeed, I am of the same opinion as you, my goal was just to describe a scenario fitting the requirements of your question, with the unfortunate side-effect of deeply changing our view of the world (but any such scenario would I guess !)
Denis
CC BY-SA 3.0
2014-12-16T15:06:14.887Z
2014-12-16T15:17:24.010Z
2014-12-16T15:17:24.010Z
Denis
<p>        Thought experiment:<br>
<strong>Which data could convince experts</strong>, beyond reasonable doubts, <strong>about their origin outside our universe?</strong> From which margin should an expert consider such claim seriously?</p>

<p>For example, if one presented factorization of a billion-numbers run starting at 2<sup>1024</sup>, with proofs of primality of all factors (that wouldn’t be a very large thing neither by amount of information nor by complexity to verify wrt 21st-century standards), it would be spectacular. But who knows which exactly complexity of integer factorization is? Who knows wasn’t factorization of <em>this namely run</em> facilitated by some mathematical coincidences?</p>

<p>But there are many problems with proven lower bounds on complexity that are really prohibitive, some of which hinder even application of powerful quantum computers (still hypothetical), and some problems are algorithmically undecidable in principle.</p>

<p>P.S. please, do not post answers based on trivia about <a href="https://en.wikipedia.org/wiki/Transcomputational_problem" rel="nofollow">transcomputational problems</a>. Ī’m interested only in answers containing insights about how a (hypothetical) piece of information <em>can be defended against the hypothesis</em> that some (still unknown to experts) mathematics was employed to produce it.</p>

<hr>

<p><em>Update:</em> (related to @usul’s answer). We do not consider a totally abstract problem. Alleged “god” may use information from our civilization in input data for the problems solved, such as to use long pieces of “our” predefined data, presumedly random, to convince us that particular input data were not specially arranged.</p>

CC BY-SA 3.0
2014-12-16T13:16:02.090Z
There is no such thing as an expert on what does not belong to this
universe. But this being stated, what about a device that answers the
halting problem in constant finite time. That might be an interesting
start, provided it comes with a proof that the device is indeed
correct. You should read Lewis Padgett, it is fun. *All mimsy were
ye borogoves / And ye mome raths outgrabe.*
babou
CC BY-SA 3.0
2014-12-16T13:22:50.110Z
How could such a device possibly come with a proof that it is indeed correct? Because halting is undecidable, it would be impossible to simulate the device using a TM - but if we could "describe" the workings of the device in a proof then surely we could simulate it?
Tom van der Zanden
CC BY-SA 3.0
2014-12-16T13:41:52.510Z
@Tom van der Zanden: presumed “god” hasn’t necessarily be omnipotent, or (more concretely) able to solve (certain) algorithmically undecidable problems. They just have to demonstrate computational abilities grossly superior to ones plausible for a being in our universe.
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T13:47:55.897Z
@Tom van der Zanden: dealing with your question closer, the “god” can provide **a proof** that an algorithm with particular input never halts.
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T15:05:56.820Z
A good strategy for a TCS-oriented God in a discrete deterministic Universe is the following: You, human, take this enclosed envelope; now pick your favourite random stream of bits generated by radioactive decay and write them down; open the envelope and compare them to the ones I predicted. :-D :-D
Marzio De Biasi
CC BY-SA 3.0
2014-12-16T15:20:58.590Z
@Marzio De Biasi: yes, **in a discrete deterministic Universe ☹** See my comment to Denis’s answer.
Incnis Mrsi
CC BY-SA 3.0
2014-12-16T15:58:39.987Z
@babou: my leading formulation was somewhat ambiguous. As follows from the context (where Ī asked and how Ī tagged it), as well as from example, Ī don’t seek *here* expertise in *theomatics* or *exocosmology*. Here Ī seek expertise about **limits** to extract, process, and possibly guess information by **any being obeying laws of our world.**
Incnis Mrsi
CC BY-SA 3.0
2014-12-17T09:14:05.510Z
How is this a research-level question about theoretical computer science?
David Richerby
CC BY-SA 3.0
2014-12-17T09:27:12.070Z
@David: Don’t care about your downvote, but Ī’d appreciate if you pointed to some established papers or textbooks that consider this… eh… long-researched question. And not to popular fiction works, of course.
Incnis Mrsi
CC BY-SA 3.0
2014-12-17T09:49:34.150Z
@IncnisMrsi You're welcome to try to correlate downvotes against the arrival of negative comments but do bear in mind that you do not actually know who voted. And I rather think that it is *your* job to demonstrate that your question is [on-topic](http://cstheory.stackexchange.com/help/on-topic).
David Richerby
CC BY-SA 3.0
2014-12-18T09:21:34.980Z
This is not a TCS question and is not a week-defined mathematically rigorous question, please read our [about] and [help/on-topic] to understand the scope of this site. We also don't like posts whose goal is to solicit opinion. I am voting to close as off-topic. (It might be OK to post it on [philosophy.se] or a similar site.)
Kaveh
CC BY-SA 3.0
2014-12-18T10:46:28.320Z
@Kaveh: Ī don’t deem the question is strictly defined mathematically (if Ī did, Ī’d ask it at one of two mathematical SE sites). But Ī won’t go to Philosophy with it, and even didn’t tag it as [tag:philosophy] although was aware about it. Ī request only complexity-based, hard physical, and mathematical arguments, not opinion of philosophizers, adepts of minority theories, cranks, nor am Ī interested with disputes considering unscientific doctrines of any kind. Sorry if the title appeared (unnecessarily) inflammatory; feel free to remove the noun **-** -- from it.
Incnis Mrsi
CC BY-SA 3.0
2014-12-18T15:31:37.637Z
If you don't like to ask on another site it is your decision. In any case this is off-topic on this site.
Kaveh
CC BY-SA 3.0
2014-12-18T15:43:39.980Z
@Kaveh: is science-based analysis of possibilities and limitations for production of (verifiable) knowledge *in our universe* off-topic? What is the [tag:physics] tag for?
Incnis Mrsi
CC BY-SA 3.0
2014-12-18T15:55:07.857Z
This is not aTCS question as I said. Read the description of the scope of the site in the links I have provided above if you want to understand what we mean by TCS.
Kaveh
CC BY-SA 3.0
2014-12-18T23:17:10.360Z
I don't understand what is the objection to being able to guess random numbers?
Sasho Nikolov
CC BY-SA 3.0
2014-12-21T23:14:43.533Z
_is science-based analysis of possibilities and limitations for production of (verifiable) knowledge in our universe off-topic?_ — **YES.**
Jeffε
CC BY-SA 3.0
2014-12-22T03:42:41.033Z
@SashoNikolov, that would be one answer, but the interest of the question (if any) is in examples of weaker oracles or pieces of data that are convincing.
usul
<cc.complexity-theory><physics>
How could God authenticate in one message?
Incnis Mrsi
# How could God authenticate in one message?

(Asked by: username_0 on 2014-12-16)

Thought experiment:  
**Which data could convince experts**, beyond reasonable doubts, **about their origin outside our universe?** From which margin should an expert consider such claim seriously?

For example, if one presented factorization of a billion-numbers run starting at 21024, with proofs of primality of all factors (that wouldn’t be a very large thing neither by amount of information nor by complexity to verify wrt 21st-century standards), it would be spectacular. But who knows which exactly complexity of integer factorization is? Who knows wasn’t factorization of *this namely run* facilitated by some mathematical coincidences?

But there are many problems with proven lower bounds on complexity that are really prohibitive, some of which hinder even application of powerful quantum computers (still hypothetical), and some problems are algorithmically undecidable in principle.

P.S. please, do not post answers based on trivia about [transcomputational problems](https://en.wikipedia.org/wiki/Transcomputational_problem). Ī’m interested only in answers containing insights about how a (hypothetical) piece of information *can be defended against the hypothesis* that some (still unknown to experts) mathematics was employed to produce it.

---

*Update:* (related to @usul’s answer). We do not consider a totally abstract problem. Alleged “god” may use information from our civilization in input data for the problems solved, such as to use long pieces of “our” predefined data, presumedly random, to convince us that particular input data were not specially arranged.

**Tags:** cc.complexity-theory, physics
> **Comments:**
> **username_1**: There is no such thing as an expert on what does not belong to this universe. But this being stated, what about a device that answers the halting problem in constant finite time. That might be an interesting start, provided it comes with a proof that the device is indeed correct. You should read Lewis Padgett, it is fun. *All mimsy were ye borogoves / And ye mome raths outgrabe.*  
> **username_2**: How could such a device possibly come with a proof that it is indeed correct? Because halting is undecidable, it would be impossible to simulate the device using a TM - but if we could "describe" the workings of the device in a proof then surely we could simulate it?  
> **username_0**: @Tom van der Zanden: presumed “god” hasn’t necessarily be omnipotent, or (more concretely) able to solve (certain) algorithmically undecidable problems. They just have to demonstrate computational abilities grossly superior to ones plausible for a being in our universe.  
> **username_0**: @Tom van der Zanden: dealing with your question closer, the “god” can provide **a proof** that an algorithm with particular input never halts.  
> **username_3**: A good strategy for a TCS-oriented God in a discrete deterministic Universe is the following: You, human, take this enclosed envelope; now pick your favourite random stream of bits generated by radioactive decay and write them down; open the envelope and compare them to the ones I predicted. :-D :-D  
> **username_0**: @Marzio De Biasi: yes, **in a discrete deterministic Universe ☹** See my comment to Denis’s answer.  
> **username_0**: @babou: my leading formulation was somewhat ambiguous. As follows from the context (where Ī asked and how Ī tagged it), as well as from example, Ī don’t seek *here* expertise in *theomatics* or *exocosmology*. Here Ī seek expertise about **limits** to extract, process, and possibly guess information by **any being obeying laws of our world.**  
> **username_4**: How is this a research-level question about theoretical computer science?  
> **username_0**: @David: Don’t care about your downvote, but Ī’d appreciate if you pointed to some established papers or textbooks that consider this… eh… long-researched question. And not to popular fiction works, of course.  
> **username_4**: @IncnisMrsi You're welcome to try to correlate downvotes against the arrival of negative comments but do bear in mind that you do not actually know who voted. And I rather think that it is *your* job to demonstrate that your question is [on-topic](http://cstheory.stackexchange.com/help/on-topic).  
> **username_5**: This is not a TCS question and is not a week-defined mathematically rigorous question, please read our [about] and [help/on-topic] to understand the scope of this site. We also don't like posts whose goal is to solicit opinion. I am voting to close as off-topic. (It might be OK to post it on [philosophy.se] or a similar site.)  
> **username_0**: @Kaveh: Ī don’t deem the question is strictly defined mathematically (if Ī did, Ī’d ask it at one of two mathematical SE sites). But Ī won’t go to Philosophy with it, and even didn’t tag it as [tag:philosophy] although was aware about it. Ī request only complexity-based, hard physical, and mathematical arguments, not opinion of philosophizers, adepts of minority theories, cranks, nor am Ī interested with disputes considering unscientific doctrines of any kind. Sorry if the title appeared (unnecessarily) inflammatory; feel free to remove the noun **-** -- from it.  
> **username_5**: If you don't like to ask on another site it is your decision. In any case this is off-topic on this site.  
> **username_0**: @Kaveh: is science-based analysis of possibilities and limitations for production of (verifiable) knowledge *in our universe* off-topic? What is the [tag:physics] tag for?  
> **username_5**: This is not aTCS question as I said. Read the description of the scope of the site in the links I have provided above if you want to understand what we mean by TCS.  
> **username_6**: I don't understand what is the objection to being able to guess random numbers?  
> **username_7**: _is science-based analysis of possibilities and limitations for production of (verifiable) knowledge in our universe off-topic?_ — **YES.**  
> **username_8**: @SashoNikolov, that would be one answer, but the interest of the question (if any) is in examples of weaker oracles or pieces of data that are convincing.  

---

## 4 answers

### Answer by username_9 on 2014-12-21. Score: 3

God could (a) provide a proof that factorization was hard and (b) use the idea of the OP to show us that He can factor large numbers.

(Of course, this doesn't work if you think factorization is easy or it's possible to build quantum computers. But then God could choose a different problem to demonstrate with.)

> **Comments:**
> **username_8**: Are you allowing some sort of interaction? Otherwise, I don't see how to accomplish (b).  
> **username_9**: No, I'm not. God (a) sends a proof that some kind of randomized problem is hard. (b) solves the randomized problem for the first ten thousand instances, where the random numbers are given by the bits of $\pi$. Even God shouldn't be able to tailor a problem so that the bits of $\pi$ give easily solvable instances, and where the problem description is short compared to the number of bits of $\pi$ that are used.  
> **username_8**: I agree that this would be subjectively convincing, but as the original question points out, such a problem *could* be coincidentally easy for those problems or bits of $\pi$. Maybe it's even likely that among all hard problems there exists one where the first 10,000 such instances are easy. Whereas with interaction it seems we can get a closer-to-formal guarantee that either the oracle knows the random bits we are using, or can solve problems in PSPACE.  
> **username_9**: @usul: I think it's much more likely that an advanced civilization has an undetectable surveillance device that can observe your coin flips than that the bits of $\pi$ are sufficiently non-random that there is a problem with a short description that the bits of $\pi$ can solve that beats the information-theoretic bound that would make it impossible with random bits that an adversary knew ahead of time.  
> **username_10**: While He's at it, He can also provide a proof that the digits of $\pi$ are indeed random.  
> **username_0**: @Denis: why not to prove that all our mathematics is wrong then? Digits of any specific computable number (π or else) aren’t random in any sense of the word (you still need much things to learn), unless our theories are contradictory and we can prove *both* they “are random” and “aren’t random” by logical principle of explosion.  
> **username_0**: @Peter (related to comments, not body text): use of a computable sequence of input data requires a proof that this particular sequence hasn’t special weakness wrt to problem solved. Ī’d be more convinced with input data constructed of published information of ancient origin (literary texts, star catalogs, weather data…), with presumedly low redundancy (that can be achieved by using hashes at expense of injectivity), than with digits of π or so.  
> **username_10**: @IncnisMrsi Of course I don't mean random in the computable sense but in the distribution of digits: normality of $\pi$ is an open problem. Try interpreting the answers in a way that makes sense before assuming your interlocutor is wrong. And once again, even if he is wrong, avoid unnecessary comments like "you have much to learn", it is really unpleasant and contrary to the website's policy.  

---

### Answer by username_8 on 2014-12-16. Score: 1

Any given piece of data is finite, so it seems difficult for such data to be evidence of asymptotically good computational abilities. Examples like your list of factorizations seem to be subjective (though in practice probably quite convincing that one can solve the problem).

One note is that for any problem outside of NP, we do not even have the computational resources to read or verify a proof that the oracle provides. So in this sense an oracle more powerful than NP is unable to convince us of this fact by providing data to us.

However, if we are given the ability to query the oracle with inputs of our choice, then intuitively this corresponds to the complexity class [IP](http://en.wikipedia.org/wiki/IP_(complexity)), so we should be able to convince ourselves that the oracle can solve problems in PSPACE. Of course this is with the finite-data caveat: We can only ever ask questions up to a certain size input. But then again, we only ever care about answering questions up to a certain size input.

> **Comments:**
> **username_0**: Could you clarify please? Do you insist without response to our *challenge* any alleged “god” is unable to quell your doubts about beyond-universe computational abilities?  
> **username_11**: Just a short remark on an interactive case: for me He would be more credible, if He started the communication with the proof that a PSPACE problem A requires exponential time to solve on average case, for some efficiently samplable distribution D. Then, I would sample from this distr. a bunch of instances of size 2^30 and use IP protocol for him to convine me he knows answer. I'd be convinced enough, even though instance size is finite. Can similar thing be done with one shot massage, assuming some problem in NP is hard on average?  
> **username_8**: @IncnisMrsi, I don't insist on anything, but yes, if we model ourselves as polynomial-time Turing Machines, then we can only check proofs of NP statements by definition; we cannot always check harder proofs.  
> **username_0**: Hope @usul sees Ī edited the question providing a “virtual challenge protocol”.  
> **username_9**: @Jarosław: We know already that permanent (modulo a prime) is as hard in the average case as it is in the worst case, we know an IP protocol for permanent, and we know that permanent is NP-hard.  

---

### Answer by username_10 on 2014-12-16. Score: 0

To account for your additional requirement of a nondeterministic universe, another way to go would be arbitrary precision information about physical constants. For instance the code of a Turing Machine which computes gravitational constant $G$ (in $m^3·kg^{−1}·s^{−2}$) with arbitrary precision.

It would be indeed surprising that such a machine exists, but assume we get one with this guarantee written on it. At the beginning we would just be able to test that the machine matches the current precision on $G$, which is nothing extraordinary. But as technology advances and measurements gets finer and finer, we would be convinced with increasingly high precision that the machine indeed computes $G$.Therefore, assuming scientific progress goes on, we could reach arbitrary precision on the accuracy of the machine, and on the fact that it is "supernatural", because at least as advanced as any level of knowledge we can achieve.

This assumes we are never able to *prove* that the machine computes $G$, which is based on the assumption that there is no computational link between physical constants (here $G$, and the various constants used to define unities, like the speed of light $c$). This assumption is reasonable in the current state of knowledge, but we never know...

> **Comments:**
> **username_0**: OMG… *c* in **metres per second?** Putting aside (dubious) merits of the concept itself, are you serious about **this concrete constant?**  
> **username_10**: I realized the mistake while you were typing your comment ;) changed it to G  
> **username_0**: So… which verification procedure do you envisage?  
> **username_10**: the verification time would depend of the confidence you want (which, again, can never be 100%). At the current speed of progress it is actually quite reasonable: any digit of precision gained on the measure of $G$ divides by ten the probability of failure.  
> **username_0**: So, any guy able to guess, say, next three digits of *G* (with *a priori* probability about $10^{-3}$) will be deified. Not a good prospect for rationally thinking humans.  By the way, @Denis, are you aware about precision of the currently accepted **definition of kilogram?**  
> **username_10**: If you are not happy with $10^{-3}$ you can wait longer... The fact that it is a Turing Machine also adds weight to it: once the number of digits correctly guessed greatly exceeds the size of the machine, things cannot be attributed to chance anymore, but there is something weird at work.  
> **username_10**: about the kilogram yes I know, if you want replace $G$ with Planck time or another one, I'm not a physicist so I didn't choose the optimal constant right away sorry  
> **username_0**: Also, the concept shows that Denis has very little notion about physical quantities. IMHO a waste of time.  
> **username_10**: Thank you for your kindness, my last comment was indeed about Kolmogorov complexity, and I now regret having wasted my time trying to give you a satisfying answer. You are basically asking for "what would be an impossible piece of data", and then smugly bash people trying to cope with your expectations. Please read the chart of this website before continuing interacting.  
> **username_0**: Ī retracted that part of my comment, since (mathematical) nature of dimensionless physical constants is unknown to me to the same degree as to you. But idea to extract practical amounts of information from physical *constants* is risible.  
> **username_9**: If we'll never actually be able to verify more than around 20 digits of physical constants, what good does knowing hundreds of digits do us?. This will convince us that the message comes from a more advanced civilization, but not God—anything we can verify, an advanced civilization can measure.  
> **username_10**: Indeed, the additionnal assumption needed for this to work is that given enough time, humanity will reach any given level of civilization. So asymptotically, it will get convinced (as time tends to infinity) that the message was not from another civilization.  
> **username_9**: @Denis: There are only a finite (and relatively small) number of digits of any physical constant that can be measured *even if you used the entire space and mass of our galaxy to build a measuring device.* There is no way of distinguishing the prediction of the value of a physical constant from a very, very, lucky guess.  
> **username_10**: @PeterShor This is a nice objection. Indeed, if there is a maximum of digits that is reachable by any civilization, then the message could have been sent by such a "maximally advanced" (relatively to this measure) civilization. The idea was to find an objective "measure" of advancement of civilization, such that the "impossible" message would be a machine that can surpass every fixed level if run long enough. Degree of precision on physical constants (i.e. on relations between them) was an imperfect candidate because of the absolute bound you mention, maybe something else can do the job.  

---

### Answer by username_10 on 2014-12-16. Score: 0

I am not sure it is in the spirit of your question, but here is a possible lead: a computer which acts as an "all-powerful mathematician", or for that matter, all powerful knowledge in general. This would be a computer with which we can dialogue, and ask it questions like "what is the answer of the Riemann hypothesis". The computer would give the answer and justify it by intuition-level arguments, that can be refined at the will of the questioner, all the way to formal proof if necessary.
Same thing if the results are independent, or if the question does not make sense, the computer would be able to explain it to the questioner in the best possible way for him to get convinced of that.
Any question could be allowed, as "What is the issue with dark matter? Can we design an experiment to settle the question?", and so on...

This interactive device, all-knowing but communcating on a good level for our intuition, would be a good way to violate all that we know about the world. It is able to solve any problem humans can ask themselves, at least any problem for which there is a solution which can be displayed to us in a convincing way, and so in some sense it is the best possible "god-authentification".

This is beyond your (presumable) limitation of a finite piece of data, but we can additionnally respect this condition with this fix:
This device would only work for a finite time, say a year, during which many people (including experts in various fields) could come to question it. During this time, the inside of the machine is sealed and we cannot see the mechanism, it is a blackbox. After "expiration", the lock is opened, and we discover that the answers were hardcoded in the right order, separated by predefined time intervals, and the computer was just reading them.

This is an absolute finite piece of data, that not only "knew" the answers to all the questions we could think of in one year, but additionally "knew" exactly what questions were going to be asked and when. The probability of chance for this can be neglected (such a probability will always exist anyway if the data needs to be finite).

> **Comments:**
> **username_0**: Interesting, but the “fix” is impractical. After the black box device is manufactured, it can, generally, succeed only in a tiny subset of all possible futures, namely, where examiners asked only questions with answers provided inside the black box. Or, maybe, Denis expects that God must *influence mind of examiners* to make them ask only right questions?  
> **username_10**: The "outside of this universe" phenomenon I use here is omniscience (this is only one possible way to go about your question, the other discussions were about computational power which is an equally valid track), which if exists necessarily contradicts free will.  
> **username_0**: Ī do not believe in uniqueness of future. Yes, your scenario would make me to reconsider my position, and… Ī’d be more astonished by such argument for determinism than by the very fact that God opted to contact the humankind.  
> **username_10**: Indeed, I am of the same opinion as you, my goal was just to describe a scenario fitting the requirements of your question, with the unfortunate side-effect of deeply changing our view of the world (but any such scenario would I guess !)  

---

