I found this paper to be an excellent discussion on the implications that Physics has on the complexity question, http://www.scottaaronson.com/papers/npcomplete.pdf