On computational complexity of construction of \(c\)-optimal linear regression models over finite experimental domains (Q2913226)

Consider the general linear regression model with uncorrelated errors, an \(m\)-dimensional parameter \(\beta \), and a finite rational experimental domain representing the set of all permissible regressors. Let \textbf{ {AOD}} (\textbf{ {EOD}}) be the following decision problem: Given a rational \(m\)-dimensional vector \(c\) and a positive rational threshold \(S^2\), decide whether there exists an approximate (exact) experimental design, such that the normalized variance of the best linear unbiased estimator of \(c^T\beta \) is at most \(S^2\).NEWLINENEWLINEIn the paper, the authors discuss the facts that \textbf{ {AOD}} is a co-recursively enumerable problem belonging to \textbf{ {P}}, and \textbf{ {EOD}} is an \textbf{ {NP}}-complete problem decidable in exponential time. Next, the authors show that \textbf{ {AOD}} is \textbf{ {P}}-complete which, assuming \(P \neq NC\), implies that \textbf{ {AOD}} has no efficient parallel implementation. Finally, the authors formulate complexity-theoretic implications of the fact that any instance of \textbf{ {AOD}} can be transformed to a particular linear program, and any instance of linear programming can be transformed to a particular instance of \textbf{ {AOD}}.NEWLINENEWLINEThe results presented in the paper are potentially very interesting for the theory of optimal experimental designs, because they provide limits on achievable efficiency of optimal design algorithms.