Sorry for leaving you on a cliffhanger :(
The post was already getting too complex and I didn't want to bring the whole NP-hard stuff. I may write another post entirely about complexity classes :D