Establishing determinantal inequalities for positive-definite matrices

Let A be an n × n matrix, and S be a subset of N = {1,2,..., n}. A[S] denotes the principal submatrix of A which lies in the rows and columns indexed by S. If α = {α₁, ..., α_p} and β = {β₁,...,β_q} are two collections of subsets of N, the inequality α ≤ β expresses that Π^p _{i = 1} det A[α_i] ≤ Π^q _{i = 1} det A[β_i], for all n × n positive-definite matrices A. Recently, Johnson and Barrett gave necessary and sufficient conditions for α ≤ β. In their paper they showed that the necessary condition is not sufficient, and they raised the following questions: What is the computational complexity of checking the necessary condition? Is the sufficient condition also necessary? Here we answer the first question proving that checking the necessary condition is co-NP-complete. We also show that checking the sufficient condition is NP-complete, and we use this result to give their second question the following answer: If NP ≠ co-NP, the sufficient condition is not necessary.