The ever increasing size of current datasets has made computation an essential aspect of the design of statistical procedures. Yet, current notions of statistical optimality rely on information theoretic considerations that completely ignore the computation question. In this work, we develop a new notion of optimality among computationally efficient methods. Building on average-case reductions from the planted clique problem, we establish optimality of various testing procedures in the context of sparse principal component analysis and quantify the statistical price to pay for computational efficiency. [Joint work with Quentin Berthet]