One thing I have been looking into for difficulty control is the possibility of setting the perlin function itself to scale with difficulty. Perlin complexity scales exponentially with dimension of the seed, so this might be a nice place to inject computational difficulty. I think that it would make more sense to increase complexity of frame calculation as opposed to increasing complexity of map generation (so that we never get into a situation where a user can't start a game because they don't have sufficient hardware to generate a map in reasonable time) but I'm not really sure if this is a better approach or not. I could imagine a similar situation where users' framerates are throttled to something annoyingly low simply because they can't calculate the perlin quickly enough to maintain.
What was that? I only see a bunch of words with no sense. Perlin function has no scale difficulty. What does it mean a "perlin complexity"? Perlin noise computation is not related to the map size it is always calculated from the 4 nearest points. And we aren't looking where to inject computation difficulty it is not a PoW currency.