¿Podemos decidir si un permanente tiene un término único?

Supongamos que se nos da una matriz n por n, M, con entradas enteras. ¿Podemos decidir en P si hay una permutación tal que para todas las permutaciones tenemos ?$\sigma$$\pi\ne\sigma$$\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)}$

Observaciones Por supuesto, se puede reemplazar el producto con una suma, el problema sigue siendo el mismo.

Si la matriz puede tener solo 0/1 entradas, entonces obtenemos el problema Bipartite-UPM que está incluso en NC.

Editar: Decidir si el término más pequeño es único es NP-hard si permitimos reducciones aleatorias. De hecho, yo quería plantear esta cuestión, ya que habría ayudado a resolver este uno. Ahora resultó que esto es NP completo, así que permítanme esbozar la reducción a nuestro problema. Imagine que la entrada es una matriz cero-uno (podemos suponer eso) y reemplace las entradas cero con números reales aleatorios entre 2 y 2 + 1 / n. Ahora, en esta nueva matriz con alta probabilidad, el término más pequeño es único si y solo si la matriz original es permutable a la forma triangular superior.

Editar: preguntas similares:

En un gráfico ponderado de borde, ¿hay un ciclo hamiltoniano con un peso único?

Si tenemos un CNF con pesos asignados a cada asignación variable / satisfactoria, ¿hay una asignación única que satisfaga el peso?

Estos son, por supuesto, al menos NP-hard. ¿Son estos problemas equivalentes al original o son más difíciles?

Buen problema! No es difícil dar una reducción que muestre que, si uno pudiera resolver su problema, también podría resolver el siguiente problema, llámelo SUMA AISLADA DEL SUBSET:

Dados los enteros a ₁ , ..., a _n , ¿hay un subconjunto S de las a _i cuya suma no es compartida por ningún otro subconjunto?

La reducción funciona reduciendo primero SUMA DE SUBSET AISLADA a COINCIDENCIA PERFECTA AISLADA, donde dado un gráfico bipartito ponderado G, queremos encontrar una coincidencia perfecta cuyo peso no sea compartido por ninguna otra coincidencia perfecta. Esta reducción es simple: para cada i, crear un 2x2 completa subgrafo G _i en G, tal que cuál de las dos posibles emparejamientos que elegimos para G _i codifica nuestra elección de si o no una _i está en el conjunto S.

A continuación, reduzca la PARTIDA PERFECTA AISLADA a su problema de la siguiente manera:

1. Para todo i, j, si el borde (i, j) existe y tiene un peso w _ij , establezca M _ij : = exp (w _ij ). (Esto convierte las sumas en productos).
2. Para todo i, j, si el borde (i, j) no existe, establezca M _ij : = 0.
3. Rellene M para asegurarse de que hay dos o más permutaciones π de modo que Π M _{i, π (i)} = 0. (Esto descarta soluciones espurias que no corresponden a ninguna coincidencia perfecta en G.)

Ahora, SUBSET SUMA AISLADA ciertamente parece que es al menos NP-hard, ¡y tal vez sea aún más difícil que eso (el límite superior obvio es solo Σ ₂ P)! Además, tal vez se podría demostrar que SUMA SUBSET AISLADA es NP-hard usando una reducción aleatoria de estilo Valiant-Vazirani. Esto, sin embargo, es un desafío que le dejo a otra persona ...