Two referees strongly support the paper, one referee sees this paper marginally below the acceptance threshold. After re-reading the paper, the discussions and the rebuttal, I come to the conclusion that this paper does contain relevant contributions to the problem of formalizing the concept of interpretability by exploring connections with computational complexity. Further, I think that most points of criticism have been addressed in a convincing way in the rebuttal. So I recommend acceptance.