Você consegue identificar a soma de duas permutações no tempo polinomial?

29

Recentemente, houve duas perguntas feitas no cs.se que estavam relacionadas ou tiveram um caso especial equivalente à seguinte pergunta:

Suponha que você tenha uma sequência de números tais que Decomponha-o na soma de duas permutações, e , de , de modo que ,. $a_1, a_2, \ldots a_n$ $n$ $\sum_{i=1}^n a_i = n(n+1).$ $\pi$ $\sigma$ $1 \dots n$ $a_i = \pi_i + \sigma_i\,$

Existem algumas condições necessárias: se o estiver classificado de forma que devemos ter $a_i$ $a_1 \leq a_2 \leq \ldots \leq a_n\,$

\sum_{i = 1}^{k} a_{i} \geq k (k + 1) .

$\sum_{i=1}^k a_i \geq k(k+1).$

No entanto, essas condições não são suficientes. Da resposta a esta pergunta de math.se que fiz, a sequência 5,5,5,9,9,9 não pode ser decomposta como a soma de duas permutações (pode-se ver isso usando o fato de que 1 ou 5 só podem ser emparelhado com 4).

Então, minha pergunta é: qual é a complexidade desse problema?

cc.complexity-theory ds.algorithms co.combinatorics np-hardness permutations Peter Shor
fonte

Aliás, uma variação simples veio à minha mente e não tenho certeza sobre sua complexidade. Você consegue identificar a soma livre de ponto fixo de duas permutações no tempo polinomial? (É necessário que as duas permutações discordam em cada posição ie para todos )

π_{i} \neq σ_{i}

$\pi_i \ne \sigma_i$

i

$i$

Mohammad Al-Turkistany

20

Não, você não pode identificar a soma de duas permutações no tempo polinomial, a menos que P = NP. Seu problema é NP-completo, pois a versão de decisão do seu problema é equivalente ao problema NP-completo - Correspondência Numérica com somas de destino: $2$

Entrada: Sequência de de números inteiros positivos, , para $a_1, a_2, \ldots a_n$ $\sum_{i=1}^n a_i = n(n+1)$ $1 \le a_i \le 2n$ $1 \le i \le n$

Pergunta: Existem duas permutações e tais que para ? $\psi_1$ $\psi_2$ $\psi_1(i)+\psi_2(i)= a_i$ $1\le i \le n$

Na referência, uma variante severamente restrita de NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) demonstrou ser fortemente NP-completa.

RN3DM, Dado um multiset de números inteiros e um número inteiro tal que , existem duas permutações e tais que , para ? $U = \{u_1, . . . , u_n\}$ $e$ $\sum_{j=1}^n u_j + n(n + 1) = ne$ $\lambda$ $\mu$ $u_j + \lambda( j ) + \mu( j ) = e$ $j = 1, . . . , n$

Há uma redução fácil de RN3DM para Correspondência Numérica com problema de somas de destino: Dada uma instância de RN3DM. Construímos a instância correspondente criando para $2$ $a_i= e-u_i$ $1 \le i \le n$

W. Yu, H. Hoogeveen e JK Lenstra. Minimizar a produção em uma loja de fluxo de duas máquinas com atrasos e operações de unidade de tempo é difícil para NP . Journal of Scheduling, 7: 333–348, 2004

EDITAR 1º de outubro : Seu problema é chamado Soma de Permissão. Está listado desde 1998 em OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION por Steve Hedetniemi.

Mohammad Al-Turkistany
fonte

2

Obrigado pela resposta. Eu respondi a um dos problemas no cs.se que inspirou esse (que não estava em um formulário respondido diretamente por sua referência), mas acho que você deve ter a primeira chance de responder ao segundo, já que a resposta é dada em sua referência.

precisa

Muito obrigado Peter. Fico feliz por poder ajudá-lo. Eu acho que você produzirá uma resposta melhor. Então, por favor, vá em frente e responda a essa pergunta também.

Mohammad Al-Turkistany

Aqui está a declaração do problema, como apareceu na página da Web acima: SUMOS DE PERMUTAÇÃO [Cheston, 198X] INSTANCE: Uma matriz A [1..n] de números inteiros positivos. PERGUNTA: Existem duas permutações r e s dos números inteiros positivos {1,2, ..., n} tais que para 1 <= i <= n, r (i) + s (i) = A [i] ?

Mohammad Al-Turkistany

4

Por outro lado, Marshall Hall mostrou que é possível identificar facilmente a diferença de duas permutações.

alce anônimo
fonte

14

n

$n$

Z

$\mathbb{Z}$

3

@ PeterShor Para completar, publique seu comentário como resposta separada, fornecendo um esboço de prova da completude do NP para identificar a diferença de duas permutações.

Mohammad Al-Turkistany

3

ϕ

$\phi$

π

$\pi$

\bar{π} (i) = n + 1 - π (i)

$\bar{\pi}(i) = n+1 - \pi(i)$

ϕ + π

$\phi+\pi$

{x_{1}, x_{2}, \dots, x_{n}}

$\{x_1, x_2, \ldots, x_n\}$

ϕ - \bar{π}

$\phi-\bar{\pi}$

{x_{1} - (n + 1), x_{2} - (n + 1), \dots, x_{n} - (n + 1)}

$\{x_1-(n+1), x_2-(n+1), \ldots, x_n-(n+1)\}$

{- 2, - 2, - 2, 2, 2, 2}

$\{-2,-2,-2,2,2,2\}$

{5, 5, 5, 9, 9, 9}

$\{5,5,5,9,9,9\}$

315 Peter Peter Shor

Você consegue identificar a soma de duas permutações no tempo polinomial?

Respostas: