I wonder where would be a good place to mention that we know some problems not in P, for instance Presburger arithmetic. --AxelBoldt
I've added it to Complexity classes P and NP. It should also be added to EXPTIME, whenever someone gets around to writing it. I would put it under P too, except that's more of a redirect than a real article. --LC