присвоение номера

10

Для заданных чисел таких что , существует ли присвоение чисел который является перестановкой такой, чтоA 1A 2. , , к к Σ я = 1 А я = K ( 2 K + 1 ) я 1 , я 2 , . , , , Я 2 к 1 , 2 , . , , , 2 кkA1A2...Aki=1kAi=k(2k+1)i1,i2,...,i2k1,2,...,2k

i1+i2A1i3+i4A2...i2k1+i2kAk

?

Я не могу найти эффективный алгоритм, и это решает эту проблему. Кажется, это комбинаторная проблема. Мне не удалось найти подобную проблему NP-Complete. Эта проблема выглядит как известная проблема NP-Complete или ее можно решить с помощью полиномиального алгоритма?

Gprime
источник
Достигли ли вы прогресса в решении проблемы?
Юваль Фильмус
Я забыл упомянуть, чтоA1A2...Ak
gprime
Связанная проблема , также без удовлетворительного ответа. (На первый взгляд может быть неясно, как они связаны, но если , проблема эквивалентна нахождению перестановки так что .1 2 N i 2 a - 1 - i 2 a = A iK=2N12Ni2a1i2a=Ai
Питер Шор

Ответы:

8

Эта проблема сильно NP-полная.

Предположим, что все нечетны. Тогда мы знаем, что, поскольку 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)

Эта проблема, как известно, является NP-полной; см. эту проблему cstheory.se и эту статью W. Yu, H. Hoogeveen и JK Lenstra, на которые даны ссылки в ответе.

Питер Шор
источник
6

Вот подсказка для начала: поскольку сумма всех чисел от до 2 k в точности равна k ( 2 k + 1 ) , решение возможно только в том случае, если на самом деле i 1 + i 2 = A 1 , i 3 + я 4 = A 2 и так далее. Итак, учитывая, что я 1, мы знаем, что я 2 , и так далее. Также 3 A j4 k - 1 .12kk(2k+1)i1+i2=A1i3+i4=A2i1i23Aj4k1

Юваль Фильмус
источник
Так как я должен выбрать , чтобы начать? Я не вижу решения. Но спасибо за собственность 3 A j4 k - 1i13Aj4k1
gprime
2
Если отсортированы, мы знаем 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)
Питер Шор
Да, они отсортированы. Я постараюсь использовать это ...
gprime
@PeterShor Вы также должны учитывать пределы в противоположном направлении, то есть и т. Д. И т. Д. Глядя на проблему анекдотично, кажется, что простой жадный алгоритм должен находить решения, когда они существуют, и терпеть неудачу именно тогда, когда их нет - но у меня возникают проблемы с доказательством этого. 4n1An,8n6An1+An
torquestomp
@torquestomp: Вы подняли хороший вопрос. На самом деле, ограничения с одного направления также подразумевают ограничения с другого, но это не так очевидно с первого взгляда. Я посмотрел на похожую проблему и не смог понять простой алгоритм (но мне показалось, что аналога этих критериев действительно было достаточно).
Питер Шор
0

Это проблема соответствия, и поэтому ее можно решить с помощью алгоритма Эдмонда. Смотрите википедию

Будет
источник
1
Идея Stackexchange состоит в том, чтобы иметь максимально полные ответы на вопросы. Сможете ли вы расширить свой ответ, чтобы быть больше, чем просто ссылка на Википедию?
Люк Мэтисон
Можете ли вы уточнить? Я не вижу, как я могу использовать эти алгоритмы для решения моего вопроса.
gprime
1
На самом деле, для меня это выглядит как частный случай 3-соответствия, который является NP-полным. Это не означает, что проблема ОП является NP-полной.
Питер Шор
Может ли это быть двухстороннее соответствие? Я посмотрю на 3-соответствие, чтобы увидеть, смогу ли я понять это. Спасибо!
gprime