Shor afirmou, em seu comentário à resposta anônima de alce a esta pergunta. Você consegue identificar a soma de duas permutações no tempo polinomial? , Que é -Complete para identificar a diferença de dois permutações. Infelizmente, eu não ver uma redução direta do problema da soma de permutação e é útil ter o N P redução -completeness para o problema diferença de permutação.
Diferença de permutação:
INSTANCE: Uma matriz de números inteiros positivos.
Pergunta: existem duas permutações e σ dos inteiros positivos 1 , 2 , . . . , n tal que | π ( i ) - σ ( i ) | = A [ i ] para 1 ≤ i ≤ n ?
Qual é a redução para provar a -completeness de reconhecer a diferença de dois permutações?
EDIT 2014/10/09 : comentário de Shor dá uma redução que prova -completeness quando os elementos de sequência Um são assinados diferenças. No entanto, não vejo uma redução fácil para o meu problema, onde todos os elementos de A são os valores absolutos das diferenças.
UPDATE: O problema Diferença Permutação parece ser -Complete mesmo se uma das duas permutações é sempre a permutação identidade. A prova de dureza deste caso especial é muito bem-vinda. Então, eu estou interessado na completude N P desta versão restrita:
Diferença de permutação restrita: INSTANCE: Uma matriz de números inteiros positivos.
PERGUNTA: Será que existe uma permutação dos inteiros positivos 1 , 2 , . . . , n tal que | π ( i ) - i | = A [ i ] para 1 ≤ i ≤ n ?
Atualização 2 : O problema restrito é eficientemente decidível, como mostra a resposta de mjqxxxx. A complexidade computacional do problema original não está comprovada.
EDIT 9/6/16 : Estou interessado em determinar se essa simplificação da Diferença de Permutação é NP-completa:
Diferença de Permutação Restrita:
INSTANCE : Um multiset de números inteiros positivos.
PERGUNTA : Será que existe uma permutação dos inteiros positivos 1 , 2 , . . . , n tal que A = { | π ( i ) - i | : 1 ≤ i ≤ n } ?
fonte
Respostas:
O problema restrito, onde um dos permutações é a identidade, é certamente em . Construa o gráfico bipartido em que cada vértice i ∈ V 1 = { 1 , 2 , … , n } está conectado ao (s) elemento (s) j ∈ V 2 = { 1 , 2 , … , n } de modo que | i - j | = A [ i ] . Então a permutação desejada σP i∈V1={1,2,…,n} j∈V2={1,2,…,n} |i−j|=A[i] σ existe se e somente se o gráfico tiver uma correspondência perfeita (isto é, uma correspondência com arestas), que pode ser determinada em tempo polinomial.n
fonte
Aqui está uma variação levemente interessante em que o problema é fácil: em vez de um conjunto básico de , permita qualquer subconjunto de { 1 , 2 , 4 , 8 , … } . O objetivo ainda é encontrar uma permutação π para que A = { | π ( 2 k ) - 2 k | : 2 k ∈ Ω } onde Ω{1,2,3,…,n} {1,2,4,8,…} π A={|π(2k)−2k|:2k∈Ω} Ω é o terreno estabelecido. A principal vantagem aqui é que o novo conjunto de aterramento força cada elemento de
a ser 2 k 1 - 2 k 2 para alguns k 1 , k 2 e se k 1 ≠ k 2 , então k 1 e k 2 são determinados por este diferença. Segue-se que, para cada diferença | 2 k 1 - 2 k 2 | em A , podemos inferir que π ( 2 kA 2k1−2k2 k1,k2 k1≠k2 k1 k2 |2k1−2k2| A ouπ(2 k 2 )=2 k 1 (ou ambos).π(2k1)=2k2 π(2k2)=2k1
A solução eficiente dessa variação simplificada é então mais ou menos rotineira. Comece construindo o multigráfico bipartido não direcionado onde L e R são cópias distintas do conjunto de solo e adicione arestas ( 2 k 1 , 2 k 2 ) e ( 2 k 2 , 2 k 1 ) sempre | 2 k 1 - 2 k 2 | aparece emG=(L⊔R,E) L R (2k1,2k2) (2k2,2k1) |2k1−2k2| com k 1 ≠ k 2 . Eu afirmo que o seguinte é equivalente:A k1≠k2
Na verdade, não vou provar isso por causa do tempo, mas não é tão ruim malhar sozinho. Que é direto. Que 21⟹2 é um pouco mais árduo, mas não é tão ruim quando você argumenta com o automorfismo de G, que envia cada vértice em L para sua cópia em R (e vice-versa). A prova que tenho em mente direciona as arestas em G para que todas as arestas em um ciclo sigam `` da mesma maneira em torno do ciclo '' (cada vértice não isolado tem in-degree = out-degree = 1) e, portanto, o anterior o automorfismo de G permanece um automorfismo da versão dirigida.
π é, então, escolhido de acordo com as arestas que vão de L a R .2⟹1 G L R G G π L R
Você pode colocar o algoritmo acima como uma pergunta de correspondência perfeita, e imagino que haja outras reduções no 2-SAT. Não vejo como estender essas abordagens para o problema original.
fonte