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 ?
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?
Respostas:
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:
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 ...
fonte