Ramfjord's comments

P is a strict subset of NP. If you can solve the problem in polynomial time, then you can verify a solution simply by generating it.

I believe there's some problem with assuming that, given an envelope containing X dollars, that the other envelope has a 50% chance of containing 2x, and a 50% chance of containing X/2. This step is clearly what leads us into the paradox.

Suppose you open the first envelope, and find $100, and are given the option to switch. If there is a 50/50 chance of the other envelope containing 200/50, we could easily model this problem a million times and find that it averages to 125.

The problem here is that the numbers have not been pre-determined in the start. If a naive player repeatedly played a game where the numbers are guaranteed to be 100 and 200, then the always switching strategy would be exactly the same as the always staying strategy.

In this case, let the difference between the two envelopes be x. When you switch, you have a 50% chance of losing x and a 50% chance of gaining x. There is really no problem if you define the two envelopes as differing by a fixed number, rather than one being a multiple of the other. When the two numbers have fixed, predetermined values, the two problems are the same.