Are you asserting that this would be a testable attribute of a putative omniscient god that could not be demonstrated by a simulated god? Or merely that it is an attribute that could not be simulated, even if I as an observer would have no way of telling the difference between the real thing and a sufficiently properly rigged demo?
Definitely the latter. Probably also the former, but constructing the test (or proof that such a test exists) requires math skills I don’t have and so there is some chance that it isn’t possible after all.
If you are polynomial time (BPP), then for any problem whose answer can be demonstrated to you by an interactive proof protocol with an untrusted logically omniscient prover (IP), that protocol can also be executed by a prover who is limited to PSPACE. (The set of problems that can be thus proved is also PSPACE).
Proof: for any given BPP verification algorithm (you), the prover’s task is selecting a strategy that maximizes your chance of acceptance. Which is equivalent to choosing the optimal move in a game tree with polynomial depth (because of your limited time) and constant branching factor (a branch being one bit of the prover’s message, or one bit of randomness you generate). Depth-first traversal of that tree takes little memory.
If you found two different purported gods and played them against each other (MIP) you could get a higher bound on their power, but only if you somehow knew that they weren’t colluding.
Definitely the latter. Probably also the former, but constructing the test (or proof that such a test exists) requires math skills I don’t have and so there is some chance that it isn’t possible after all.
If you are polynomial time (BPP), then for any problem whose answer can be demonstrated to you by an interactive proof protocol with an untrusted logically omniscient prover (IP), that protocol can also be executed by a prover who is limited to PSPACE. (The set of problems that can be thus proved is also PSPACE).
Proof: for any given BPP verification algorithm (you), the prover’s task is selecting a strategy that maximizes your chance of acceptance. Which is equivalent to choosing the optimal move in a game tree with polynomial depth (because of your limited time) and constant branching factor (a branch being one bit of the prover’s message, or one bit of randomness you generate). Depth-first traversal of that tree takes little memory.
If you found two different purported gods and played them against each other (MIP) you could get a higher bound on their power, but only if you somehow knew that they weren’t colluding.