I think a longer runtime for a terminating program will require more state to be kept. Every step needs to keep extra reversibility information. So I don't thi

I think a longer runtime for a terminating program will require more state to be kept. Every step needs to keep extra reversibility information. So I don't think this gives any edge on NP. I suspect that even if you waited for the universe to cool down a lot by waiting aeons and then performed computations arbitrarily slowly you'd still be limited by your starting energy (maximum bits you can write to start with). Although maybe using random bits might help somehow?