Naively it seems not to bad to me but I am totally not an expert. If you have a million bits of state, we ask if a machine will halt in a million steps, otherwise we can not be sure that the machine does not use more than a million bit of memory. This of course heavily underestimates the hardness as you can have a machine with only 20 bit that goes through a million states. This also means that the EXPTIME is not that bad because the problem size is only 20, the number of bits required to write the number of bits in the machine, not the number of bits in the machine itself.