5

This is somewhat complementary to domotorp's existing answer, explaining the first paragraph in more detail. Let's consider the tightest possible case, where $n = 2m - 1$ and there are $m^2$ A-squares and $n^2 - m^2$ B-squares. The problem is to partition the $n \times n$ grid into $n$ polyominoes of $n$ squares each, such that $m$ of the polyominoes each ...


3

This is exactly equivalent to asking the complexity of solving $\Phi(X) = C$, where $\Phi$ is a linear transformation acting on the vector space of $d \times d$ matrices. Since that vector space is $d^2$-dimensional, this has complexity $O((d^2)^3) = O(d^6)$ (or more precisely, $O((d^2)^\omega) = O(d^{2\omega})$, where $\omega$ is the exponent of matrix ...


Only top voted, non community-wiki answers of a minimum length are eligible