There is a simple solution to this which most games use and in fact is implemented within most physics engines automatically. Use a fixed timestep for updating the simulation. For general purposes, this article is typically the goto source for how to implement it: https://www.gafferongames.com/post/fix_your_timestep/​.​ . For example, with PhysX, if you use the standard API to simulate the world, it has implemented this method (or at least the same results) under the hood, it only actually updates physics at the fixed rate and all the positions you get back are interpolated. With a solution such as that, adding fast/slow time is very easy, you multiply a scalar by delta time prior to feeding it into your clock. So, for real time you multiply by 1, for half time use 0.5 and double time use 2.0. Simple solution and the time stepping behind the scenes deals with managing when the simulation should update.

While there are other potential solutions you could use, typically they involve either a significant amount of additional work and/or they end up with the types of bugs you ran into in the mentioned game. Generally speaking, the math used for games is not easily made time step independent and the above is generally the preferable solution given the general simplicity involved.

Thaumaturge said:
That is, if for example you want to increase the rate of the simulation to twice the baseline rate, then you simply run twice as many steps per frame.

I did this in a game which used variable timesteps.
The physics where mostly about constant velocity (kind of Breakout), so variable timestep did not cause much problems.
But in some cases it did, e.g. the mapping from accelerator sensors to affect things, which was not linear. For those things i did subdivide time, so the timestep got as close as possible to a fixed target.
Worked well for this simple game.

felix.speagel said:
every article I've read about integration of time in physics simulations says the \Delta tΔt should be constant or a very strange things will happen like bullets going through walls etc.

It's a good advise in general, but not the only option.
For a space game, variable timestep should be quite easy, because physics are very smooth.
If you have stacks of boxes, lots of multi body systems like ragdolls, and complex stuff, supporting a dynamic timestep becomes much harder or just unpractical.

felix.speagel said:
how to make a simulation where one can speed it up/down?

If the speed only varies slightly, e.g. we jitter back and forth between 30 and 60 Hz due to display framerate, using fixed 60Hz for physics (thus doing two physics updates in some frames) is the best option. That's what the ‘fix your timestep’ article proposes, and it is the general case.

But if speed varies a lot like with space travel, variable step is your only option, because you can not do 1000 physics updates per frame. (Well, some racing games do this actually, but that's again a constant small timestep.)
I remember a guy making a space simulator using Newton physics engine (which is a typical game rigid body engine meant to use constant timesteps), and afaik variable timestep worked for him without problems.

Regarding integration and constraint solvers, it surely helps to vary the timestep smoothly and not abruptly. So if you want to speedup by a factor of 100, it might take a second til you get there.

EDIT: In some simulations, e.g. fluid, it is quite common to analyze current state to calculate the biggest timestep we can do. So that's a form of dynamic timestep for optimization needs.
Another example is to diffuse energy over the surface of a triangle mesh. Her we can calculate a maximum ‘timestep’ from the geometry once, and use it for all steps of an iterative solver. Just a single degenerate triangle with a very short edge can increase calculation times by factors of 1000, if we really care bout perfect accuracy.

It's possible to adaptively adjust the time step to maintain a tolerable amount of error, but it requires doing some sub-steps at a smaller step to estimate the error.

felix.speagel said:
(for some game's elements it may be n^2n 2 or \frac{n}{2} 2 n ​ or something like that).

Exactly, which is why it's hard and tedious to do such scaling of the simulation.
And by doing so, the simulation will likely become even more unstable. It may assume masses remain constant, but you go to scale them all at once. Same for max/min forces for motors, etc. If some solver use previous step for an initial guess of the next step, or there are cached contacts, all those things might break. And you might not have access to all those internal details.

Maybe it's worth a try, but i don't see any benefit. After scaling things properly, the simulation will still run with the same robustness and accuracy as before.
I mean, say you make your world 10 times smaller, but you don't scale velocities, so a timestep covers 10 times the visual distance, and it looks like time is running faster.
You can achieve this way easier by making just the timestep 10 times larger. Same or less problems to expect, but less work. Though, that's just my personal guess.

Did you try to change timestep gradually, in small steps? This way cached things in the physics engine would not go totally out of reasonable ranges, and it might work well enough.
Otherwise you should talk to the devs of the physics engine you are using (if so). They might have some proper advise.

felix.speagel said:
So, in other words, we are changing the game's universe to work faster, stronger, etc. to imitate the effects of increased time speed. (I've to do some little app to test this hypotenuse)

Unfortunately that is mathematically the same as doubling the delta time, it doesn't change the inherent error of using fewer steps in the simulation. I.e. P' = P + V x T is the eventual integration and you are changing the masses by 2 which is effectively P' = P + (V x 2) x T which can be refactored as P' = P + V x (T x 2), in other words, doubled step time is equivalent to doubling all the masses used to calculate the velocity.

There are ways to perform better approximations of the underlying math but they are generally prohibitively expensive,, very difficult and still prone to blowing up. I'm not trying to say there are not other solutions here, I'm just pointing out that it is unusual for games to use them when a simplified approach exists. For instance, someone mentioned using error based metrics, that is completely viable but very often expensive when compared to the simple stepping solution.