incompletude do reconhecimento da diferença de duas permutações

21

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.NPNP

Diferença de permutação:

INSTANCE: Uma matriz de números inteiros positivos.A[1...n]

Pergunta: existem duas permutações e σ dos inteiros positivos 1 , 2 , . . . , n tal que | π ( i ) - σ ( i ) | = A [ i ] para 1 i n ?πσ1,2,...,n|π(i)σ(i)|=A[i]1in

Qual é a redução para provar a -completeness de reconhecer a diferença de dois permutações?NP

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.NPAA

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:NPNP

Diferença de permutação restrita: INSTANCE: Uma matriz de números inteiros positivos.A[1...n]

PERGUNTA: Será que existe uma permutação dos inteiros positivos 1 , 2 , . . . , n tal que | π ( i ) - i | = A [ i ] para 1 i n ?π1,2,...,n|π(i)i|=A[i]1in

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.A

PERGUNTA : Será que existe uma permutação dos inteiros positivos 1 , 2 , . . . , n tal que A = { | π ( i ) - i | : 1 i n } ?π1,2,...,nA={|π(i)i|:1in}

Mohammad Al-Turkistany
fonte
Por que não perguntar diretamente a Peter? @Peter
caozhu 21/02
Você quer dizer por email? Eu vou fazer isso.
Mohammad Al-Turkistany
Posso estar faltando alguma coisa, mas esse problema não pode ser representado como um 2-SAT e, portanto, ser resolvido no polytime? Podemos supor ao WLOG que uma das permutações é a identidade (estou assumindo aqui que A [i] é calculado ciclicamente; isso importa muito?), E então podemos representar o segundo por uma matriz . Ser uma matriz de permutação é uma conjunção das cláusulas de duas variáveis, declarando que não existem duas em uma linha ou em uma coluna; e depois dizer que a diferença está nos locais de pi (i) de i é A [i] é o OR dos dois locais possíveis em que ele pode estar.x[i,j]
Noam
@Noam Obrigado pelo seu comentário. Idéia interessante. Eu não pensei nisso. No entanto, não é óbvio para mim se isso levará ao algoritmo de tempo polinomial, especialmente porque nos é dado apenas o valor absoluto das diferenças.
Mohammad Al-Turkistany
11
Sim, parece que a diferença entre contar o intervalo ciclicamente ou em valor absoluto pode ser importante.
Noam

Respostas:

5

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 σPiV1={1,2,,n}jV2={1,2,,n}|ij|=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

mjqxxxx
fonte
Talvez esteja faltando alguma coisa, mas qualquer combinação perfeita não funcionará. Você deve provar a existência de correspondência perfeita restrita. Considere um número inteiro que ocorre duas vezes na matriz de entrada A . A combinação perfeita que corresponde à permutação deve ter duas arestas com diferença absoluta k . Seu algoritmo NÃO prova a existência dessa correspondência restrita. É isso que dificulta o problema e, possivelmente, NP-complete. kAk
Mohammad Al-Turkistany
2
@ MohammadAl-Turkistany: Eu acho que se então u i , u jV 1 estão vinculados aos nós v i + A [ i ] , v i - A [ i ] , v J + A [ j ] , v J - Um [ j ]v doisA[i]=A[j]=kui,ujV1vi+A[i],viA[i],vj+A[j],vjA[j]V2com diferenças absolutas . A correspondência perfeita incluirá pelo menos uma aresta de u ie uma aresta de u j . Cheguei à mesma conclusão algumas vezes atrás, enquanto pensava no problema original, mas seguindo outra maneira: Vi que é fácil formular o problema restrito como uma fórmula 2-SAT (se você quiser, posso adicionar uma resposta) , mas a ideia de mjqxxxx é melhor). kuiuj
Marzio De Biasi
@MarzioDeBiasi Por que essa abordagem (e a sua) não funciona no problema original (irrestrito)?
Mohammad Al-Turkistany
@mjqxxx Vejo que sua abordagem resolve o caso restrito. Por que não pode ser estendido para resolver com eficiência o problema original?
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: porque no problema original os elementos da primeira permutação (a s na versão restrito) não são fixas, e usando a mesma abordagem que você acabar com um gráfico tripartite (e na minha abordagem 2-SAT com um δ i ( n ) ( π i ( n + a [ i ] ) π i ( n - a [ i ] ) ) cláusula ... que não é uma cláusula 2-CNF). iδi(n)(πi(n+A[i])πi(nA[i]))
Marzio De Biasi
0

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 1k 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 kA2k12k2k1,k2k1k2k1k2|2k12k2|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=(LR,E)LR(2k1,2k2)(2k2,2k1)|2k12k2| com k 1k 2 . Eu afirmo que o seguinte é equivalente:Ak1k2

  1. Existe uma permutação com diferenças AπA
  2. Todo vértice em tem grau 0 ou 2G

Na verdade, não vou provar isso por causa do tempo, mas não é tão ruim malhar sozinho. Que é direto. Que 212 é 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 .21GLRGGπLR

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.

Andrew Morgan
fonte