The fact that you have to consider the complexity of the encoding scheme and not just the input and the output bit patterns is well understood in information theory. If I have an encoding scheme that has included in it a complete simulation of the universe, I can encode any video into 0 bits since the decoder will always know what I am about to request of it. The more the mapping is customized to the information you're searching for, the less complexity is needed in the input bit patterns to produce the desired output. If you go searching PI for a message, it'll probably take you longer to find it if you use the ASCII values of characters than if you use base64. You'll find it even quicker if you specify that 3='h' 1st 1='e' 4='l' 2nd 1='l' 5='o'.
This all ultimately comes back to Ockham and parameters on a model. Models with more parameters can fit more things spuriously, so you want the model with the fewest parameters that can do the job. Minimum Description Length (and MML) is a great concept https://en.wikipedia.org/wiki/Minimum_description_length
If your mapping is very complex compared to the ostensible simulator, then the mapping is actually doing most of the simulation. So the simulation is not mostly running when the ostensible simulator runs, it is running when you perform the mapping.
If you are inside the universe being simulated and think you can do that mapping, it seems unlikely that there exist enough time and space for it.
But, what if there's a law of physics inside of the simulated universe that solves exponential problems in polynomial time? You could pack a more limited universe inside of that one, if you didn't want your inhabitants to have access to it. I think that computational complexity absolutely does determine how useful a simulation is to us, but it's not meta-universal enough to do this kind of philosophy with.
If I'm interpreting it correctly it does seem to put some constraints on the nature of the simulating universe, but does not necessarily disprove the existence of it?
We can divide up the task of running a physical simulation into the part where the state is computed, and the part where the results are made visible to us in a way we understand.
We can also divide computation up into the same two pieces: the actual solving of the problem, and then the task of reading symbols off the Turing tape. Usually, we set up our definitions so that a program isn't thought to "solve" a problem unless the reading-the-answer part is trivial.
Now, for a person living inside a simulation, the reading-the-answer part would become insignificant. Why do they care if we can see in to their universe?
So, if all we want is to make a world for simulated people to live in, why not stuff all of the computational complexity into the reading-the-answer part, and then not do it? They would be perfectly happy with a jumbled-up, uninterpretable state in our world, because they would be living on the inside where it made sense.
So, if that is convincing, then allow me to pitch my universe simulating computer:
Launch two photons into space. The distance between them is the state of the simulation. If you want to look in to the state, you have to solve an incredibly hard exponential problem to map the distance to a certain corresponding wavefunction that you could make sense out of.
However, the inhabitants wouldn't care about whether or not you interpreted their state. So, as far as the simulated are concerned, two photons flying apart do make a simulation!
In my opinion the easiest way to make this reductio-ad-absurdum go away is to reject the idea that the simulated is real.
Even if there might not be a single most natural mapping, I think it makes sense to say that some mappings are more natural than others. I think there is a natural sense which is independent from human perception and intent, in which a computer running, say, a graph coloring algorithm, is doing that more than a waterfall is.
Even if there is a bijection between a collection of initial states of the waterfall with the input of program, that fits together with one between the outputs and the results of the waterfall.
I agree with this part.
I wasn't thinking specifically about P vs NP though. (if I was, I think that would be a kind of weak argument because we don't have a proof that P isn't equal to NP ? At least not yet.)
I was thinking more in terms of like, Solomonoff probability and Kolmorogov and things like that.
And even if you suppose that the universe in question has a Turing oracle, I think you would just have to go up enough levels in that hierarchy in order solve that.
Even without that though, looking at the space of permutations on N, I think it is likely that there is a natural way to talk about what things are true of "most" things in that space, and things like that, which could, I think, support at least a weak sense of degrees of naturality between mappings, even without appealing to computational complexity.
Edit: I figured I should respond to this part also:
> In fact, if the problem is right, you might even end up in a situation where they can't hook their NP-hard problem solvers together in a way that solves problems that we would consider polynomial.
I think that whatever process is needed to get the output in a form that can be used as input for other things in general should be considered to be part of the computational process. Maybe that should even be implied by the meaning of "compute".
Like, say that some computation takes a number as input in a binary representation, and outputs a number, but outputs it in ternary. If you are talking about how fast the process is on numbers, it should include the time needed to convert back to the binary representation. (Unless, of course, the computation that you are considering the process to be doing includes the "input is in binary, output is in ternary" part. If it is being considered "on numbers" though, I think it should include the conversion time to and from whatever representation of numbers is being considered to be canonical.)
If simulated universes can be "real," then we're assuming that there's a mapping between patterns of electrons in a computer (or provable theorems, if you're brave enough), and the real universe they represent. (Say, interpreting two numbers that may be stored very far apart on the chip as the positions of two particles that are, in the universe, very close together.)
The problem that this introduces is that there are no well-motivated ways that we could decide which mappings are "real," and could be "lived in." For example, we might claim that the state of the simulation must be map-able in polynomial time to some charts and pictures that a human could interpret - but an inhabitant wouldn't care.
So, since all mappings are equally motivated as far as an inhabitant is concerned, allow me to choose one that maps this grain of sand to a universe the same as ours.
Well, there you go. Our world in a grain of sand.