I wonder where would be a good place to mention that we know some problems not in P, for instance Presburger arithmetic. --AxelBoldt
I suggest two places: in Complexity classes P and NP and in EXPTIME, in both cases saying it's outside the classes being discussed. (I would say to put it under P, except that's more of a redirect than a real article). --LC