Two complexity results on c-optimality in experimental design

Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its \(\boldsymbol{\mathit{NP}}\)-completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being \(\boldsymbol{\mathit{NP}}\)-complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete.