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. Ī’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.


closed as off-topic by R B, Emil Jeřábek, Kaveh, Tsuyoshi Ito, Jeffε Dec 21 '14 at 23:13

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – R B, Emil Jeřábek, Kaveh, Tsuyoshi Ito, Jeffε
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ 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. $\endgroup$ – babou Dec 16 '14 at 13:16
  • 3
    $\begingroup$ How is this a research-level question about theoretical computer science? $\endgroup$ – David Richerby Dec 17 '14 at 9:14
  • 5
    $\begingroup$ @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. $\endgroup$ – David Richerby Dec 17 '14 at 9:49
  • 3
    $\begingroup$ I don't understand what is the objection to being able to guess random numbers? $\endgroup$ – Sasho Nikolov Dec 18 '14 at 23:17
  • 2
    $\begingroup$ is science-based analysis of possibilities and limitations for production of (verifiable) knowledge in our universe off-topic?YES. $\endgroup$ – Jeffε Dec 21 '14 at 23:14

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.)

  • $\begingroup$ Are you allowing some sort of interaction? Otherwise, I don't see how to accomplish (b). $\endgroup$ – usul Dec 22 '14 at 3:48
  • $\begingroup$ 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. $\endgroup$ – Peter Shor Dec 22 '14 at 4:15
  • $\begingroup$ 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. $\endgroup$ – usul Dec 22 '14 at 14:42
  • 1
    $\begingroup$ @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. $\endgroup$ – Peter Shor Dec 22 '14 at 15:16
  • 1
    $\begingroup$ @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. $\endgroup$ – Denis Dec 22 '14 at 23:13

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, 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.

  • $\begingroup$ 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? $\endgroup$ – Incnis Mrsi Dec 16 '14 at 13:05
  • $\begingroup$ 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? $\endgroup$ – Jarosław Błasiok Dec 16 '14 at 13:17
  • 1
    $\begingroup$ @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. $\endgroup$ – usul Dec 16 '14 at 14:15
  • $\begingroup$ Hope @usul sees Ī edited the question providing a “virtual challenge protocol”. $\endgroup$ – Incnis Mrsi Dec 16 '14 at 14:20
  • $\begingroup$ @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. $\endgroup$ – Peter Shor Dec 22 '14 at 0:20

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).

  • $\begingroup$ 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? $\endgroup$ – Incnis Mrsi Dec 16 '14 at 15:16
  • $\begingroup$ 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. $\endgroup$ – Denis Dec 16 '14 at 15:22
  • $\begingroup$ Ī 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. $\endgroup$ – Incnis Mrsi Dec 16 '14 at 15:25
  • $\begingroup$ 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 !) $\endgroup$ – Denis Dec 16 '14 at 15:29

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...

  • $\begingroup$ OMG… c in metres per second? Putting aside (dubious) merits of the concept itself, are you serious about this concrete constant? $\endgroup$ – Incnis Mrsi Dec 16 '14 at 16:16
  • $\begingroup$ I realized the mistake while you were typing your comment ;) changed it to G $\endgroup$ – Denis Dec 16 '14 at 16:22
  • $\begingroup$ So… which verification procedure do you envisage? $\endgroup$ – Incnis Mrsi Dec 16 '14 at 16:23
  • $\begingroup$ 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. $\endgroup$ – Denis Dec 16 '14 at 16:26
  • $\begingroup$ 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? $\endgroup$ – Incnis Mrsi Dec 16 '14 at 16:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.