Atribuição de número de

10

Dados números modo que há uma atribuição dos números que é uma permutação de modo queA 1A 2. . . Um k k Σ i = 1 A i = k ( 2 k + 1 ) i 1 , i 2 , . . . , I 2 k 1 , 2 , . . . , 2 kkA1A2...Aki=1kAi=k(2k+1)i1,i2,...,i2k1,2,...,2k

i1+i2A1i3+i4A2...i2k1+i2kAk

?

Não consigo encontrar um algoritmo eficiente e que resolva esse problema. Parece ser um problema combinatório. Não foi possível encontrar um problema semelhante ao NP-Complete. Esse problema parece um problema NP-Complete conhecido ou pode ser resolvido com um algoritmo polinomial?

gprime
fonte
Você fez algum progresso no problema?
Yuval Filmus
Eu esqueci de mencionar queA1A2...Ak
gprime
Problema relacionado , também sem uma resposta satisfatória. (Pode não estar claro à primeira vista como eles estão relacionados, mas se , o problema é equivalente a encontrar uma permutação de modo que .1 2 N i 2 a - 1 - i 2 a = A iK=2N12Ni2a1i2a=Ai
Peter Shor

Respostas:

8

Esse problema é fortemente NP-completo.

Suponha que todos os sejam ímpares. Então sabemos que, como é ímpar, um de e é par e o outro é ímpar. Podemos assumir que é ímpar e é par. Ao permitir e , podemos mostrar que isso é equivalente a pedindo duas permutações, e , dos números tais que .i 2 j - 1 + i 2 j = A j i 2 j - 1 i 2 j i 2 j - 1 i 2 j π j = 1Aji2j1+i2j=Aji2j1i2ji2j1i2jσj=1πj=12(i2j1+1)πσ1nπj+σj=1σj=12(i2j)πσ1nπj+σj=12(Aj+1)

Esse problema é conhecido por ser NP-completo; veja esse problema de história e este artigo de W. Yu, H. Hoogeveen e JK Lenstra mencionados na resposta.

Peter Shor
fonte
6

Aqui está uma dica para você começar: como a soma de todos os números de a é exatamente , uma solução é possível apenas se de fato , e assim por diante . Então, dado , sabemos , e assim por diante. Além disso, .2 k k ( 2 k + 1 ) i 1 + i 2 = A 1 i 3 + i 4 = A 2 i 1 i 2 3 A j4 k - 112kk(2k+1)i1+i2=A1i3+i4=A2i1i23Aj4k1

Yuval Filmus
fonte
Então, como devo escolher para começar? Não estou vendo a solução. Mas obrigado pela propriedade 3 A j4 k - 1i13Aj4k1
gprime 29/05
2
Se o estiver classificado, saberemos , , e assim por diante. Esses critérios, juntamente com , são suficientes? Se estiverem, pode haver um algoritmo simples para esse problema. 3 A 1 10 A 1 + A 2 21 A 1 + A 2 + A 3 i A i = k ( 2 k + 1 )Ai3A110A1+A221A1+A2+A3iAi=k(2k+1)
quer
Sim, eles são classificados. Vou tentar usar isso ...
Gprime
@PeterShor Você também deve considerar limites na direção oposta, ou seja, e assim por diante. Observando o problema de forma anedótica, parece que um algoritmo ganancioso simples deve descobrir soluções quando elas existem e falhar exatamente quando não existem - mas estou tendo problemas para provar isso. 4n1An,8n6An1+An
torquestomp
@torquestomp: Você está levantando um bom argumento. De fato, os limites de uma direção também implicam os limites da outra, mas isso não é de todo óbvio à primeira vista. Eu olhei para um problema semelhante e não consegui descobrir um algoritmo simples (mas também me pareceu que o analógico desses critérios era realmente suficiente).
quer
0

É um problema de correspondência e, portanto, pode ser resolvido usando o algoritmo de Edmond. Veja a Wikipédia

Vai
fonte
11
A idéia do Stackexchange é ter uma sessão de perguntas e respostas tão completa quanto razoavelmente possível. Você seria capaz de expandir sua resposta para ser mais do que apenas um link para a wikipedia?
Luke Mathieson
Você pode elaborar? Não estou conseguindo ver como posso usar esses algoritmos para resolver minha pergunta.
Gprime 31/05
11
Na verdade, para mim, parece um caso especial de 3 correspondências, que é NP-completo. Isso não significa que o problema dos OPs esteja NP-completo.
quer
Poderia ser talvez uma correspondência bipartida? Vou dar uma olhada no 3-matching para ver se consigo descobrir. Obrigado!
Gprime