Podemos decidir se uma permanente tem um termo único?

16

Suponha que recebamos uma matriz n por n, M, com entradas inteiras. Podemos decidir em P se existe uma permutação tal que, para todas as permutações , tenhamos ?σπσΠMEuσ(Eu)ΠMEuπ(Eu)

Observações É claro que se pode substituir o produto por uma soma, o problema permanece o mesmo.

Se a matriz pode ter apenas entradas 0/1, então obtemos o problema Bipartite-UPM, que é uniforme no NC.

Edit: Decidir se o menor termo é único é NP-difícil se permitirmos reduções aleatórias. De fato, originalmente eu queria fazer essa pergunta, porque teria ajudado a resolver essa questão . Agora, verificou-se que este é NP-completo, então, deixe-me esboçar a redução do nosso problema. Imagine que a entrada seja uma matriz zero-um (podemos supor isso) e substitua as entradas zero por números reais aleatórios entre 2 e 2 + 1 / n. Agora, nesta nova matriz com alta probabilidade, o menor termo é único se e somente se a matriz original for permutável à forma triangular superior.

Editar: Perguntas semelhantes:

Em um gráfico com arestas, existe um ciclo hamiltoniano com um peso único?

Se tivermos um CNF com pesos atribuídos a cada variável / tarefa que satisfaça, existe uma tarefa que satisfaça o peso exclusivo?

Naturalmente, estes são pelo menos NP-hard. Esses problemas são equivalentes ao original ou são mais difíceis?

domotorp
fonte
Sabemos se esse problema ocorre mesmo no NP? Estou tendo dificuldade em encontrar um certificado.
Mhum
@mhum: O limite superior mais óbvio é , como Scott Aaronson apontou em sua resposta. Eu não acho que um limite superior melhor seja conhecido. Σ2P
Joshua Grochow

Respostas:

13

Bom problema! Não é difícil fazer uma redução mostrando que, se alguém puder resolver seu problema, também poderá resolver o seguinte problema, chame-o SOM DE SUBSET ISOLADO:

Inteiros dadas a 1 , ..., a n , existe um subconjunto S do um i 's cuja soma não é compartilhada por qualquer outro subconjunto?

A redução funciona reduzindo primeiro o ISOLADO SUBSET SUM para ISOLADO PERFECT MATCHING, onde é fornecido um gráfico bipartido ponderado G, queremos encontrar uma correspondência perfeita cujo peso não seja compartilhado por nenhuma outra correspondência perfeita. Essa redução é simples: para cada i, crie um subgrafo completo 2x2 G i em G, de modo que qual das duas combinações possíveis que escolhemos para G i codifique nossa escolha de se um i está ou não no conjunto S.

Em seguida, reduza a CORRESPONDÊNCIA PERFEITA ISOLADA para o seu problema da seguinte maneira:

  1. Para todo i, j, se a aresta (i, j) existir e tiver peso w ij , defina M ij : = exp (w ij ). (Isso transforma as somas em produtos.)
  2. Para todos os i, j, se a aresta (i, j) não existir, defina M ij : = 0.
  3. Almofada M para garantir que haja duas ou mais permutações π tais que M i, π (i) = 0. (Isso exclui soluções espúrias que não correspondem a nenhuma correspondência perfeita em G.)

Agora, ISOLADO SUBSET SUM certamente parece que é pelo menos NP-difícil, e talvez seja ainda mais difícil do que isso (o limite superior óbvio é de apenas 2 P)! Além disso, talvez se possa provar que ISOLADO SUBSET SUM é NP-difícil usando uma redução aleatória no estilo Valiant-Vazirani. Este, no entanto, é um desafio que deixo para outra pessoa ...

Scott Aaronson
fonte
Sim, estes são equivalentes. De fato, se você verificar o problema em aberto que estou tentando resolver, poderá ver que estou vindo do problema ISOLADO PERFECT MATCHING. Talvez se possa encontrar uma redução de / para o problema da Frobenius Coin.
Domotorp 10/10/10
4
Duhhh ... Andy Drucker apontou que meu problema ISOLADO SUBSET SUM é trivial de resolver! Se alguns dos a_i são 0, não há soma única; caso contrário, considere o conjunto de todos os a_i compartilhando o mesmo sinal (positivo ou negativo). Portanto, devemos nos concentrar na correspondência perfeita e isolada.
Scott Aaronson