Consider the following problem:

  • input: pairwise distinct natural numbers $k_1,\dots,k_m$ that are all $\leq n$, and matrices $A_1,\dots,A_m \in \Bbb Q^{n \times n}$ where $m \leq n$.

  • output: a matrix $B \in \Bbb Q^{n \times n}$ such that $B^{k_i}=A_{i}$ for every $i \leq m$, if such matrix exists. If no such matrix exists, the output is None.

Is the above problem NP-hard?

It's tempting to think that we can just compute the $k_i$th root of each $A_i$ somehow and check whether they all give the same answer, but that is too slow: with matrices, there can be exponentially many roots.

  • $\begingroup$ Why are you interested in NP-hardness of this problem? What’s your original motivation? (This may answer all our clarification questions. Also, it might be the case that you didn’t take the best approach for the original problem (the lack of precision is a sign of that), and we might point you to a better one) $\endgroup$
    – Dmitry
    Nov 28 '21 at 0:20
  • 1
    $\begingroup$ @Dmitry I'm working with my colleagues on a paper where we experimentally demonstrate a new heuristic way to solve a certain problem efficiently. The most obvious approach to solve that problem is via solving the problem that I posted above, so it would be nice to show that the above problem is difficult. $\endgroup$
    – Haim
    Nov 28 '21 at 0:33
  • $\begingroup$ Idea: let $K=k_1 \times \cdots \times k_m$, then if such a $B$ exists, we must have $A_1^{K/k_1} = \cdots = A_m^{K/k_m}$. Unfortunately I don't think the converse holds, so I don't think this yields an efficient algorithm for the problem, alas. $\endgroup$
    – D.W.
    Nov 28 '21 at 0:34
  • $\begingroup$ This probably means that you are interested in it’s hardness, not NP-hardness in particular. E.g. it may be undecidable but not NP-hard. It’s not evident to me that the problem is decidable (may be evident to you though). $\endgroup$
    – Dmitry
    Nov 28 '21 at 0:56
  • $\begingroup$ @Dmitry What makes it undecidable? Assuming that you can compute all $k_1$th roots of $A_1$ (which I believe is the case), you can just compute the $k_i$th powers of each of them for each $i$ and see if any of them satisfies the desired requirements. Furthermore, given $B$ as required by the output, you can verify in polynomial time that $B$ is as required, and so this problem is in NP. Am I missing something here? $\endgroup$
    – Haim
    Nov 28 '21 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.