Scott Aaronson has a really good explainer about complexity theory and physical computing:

https://www.scottaaronson.com/papers/npcomplete.pdf

(Doing my best to ignore his abysmal politics.)