algorithm - 矩阵置换的多项式算法

Question

(无法使 sigma 符号在浏览器上看起来不错)。

对于整数n，我们将F_n标记为单射函数群

f:{1,2,3…,n}→{1,2,3…,n}

对于 nXn 阶非负值的给定矩阵 A，我们将标记:

P(A)=∑_(f∈F_n)▒〖A_(1,f(1))*A_(2,f(2)) 〗…*A_(1,f(1) )*A_(n,f(n))

设计一个多项式算法来确定是否 P(A)=0。我正在考虑在矩阵中寻找 n^2-n+1 零，然后在任何排列中，乘积中都会有零，然后总和将为零，这就是 O 的运行时间(n^2)。不确定解决方案。有什么想法吗？谢谢

例子:

Answer 1

你的问题是“有没有办法将 N 只车放在 NxN 的棋盘上，这样它们就不能互相攻击，同时避开标记的(零)方格。”的补充。

例如，如果一行或一列全为零，那么它是不可能的并且 P(A) = 0，因此寻找 n^2 - n + 1 个零并不能解决问题。

然而，这里有一个答案，它给出了这个问题的一个可爱的多项式时间解决方案:https://cs.stackexchange.com/questions/28413/how-hard-is-this-constrained-n-rooks-problem