Вероятность генерации желаемой перестановки случайными перестановками

10

Я заинтересован в следующей проблеме. В качестве входных данных нам дается «целевая перестановка» , а также упорядоченный список индексов i 1 , , i m[ n - 1 ] . Затем, начиная со списка L = ( 1 , 2 , , n ) (т. Е. Перестановки тождеств), на каждом временном шаге t [ m ] мы меняем элемент i t h t в LσSNя1,...,ям[N-1]Lзнак равно(1,2,...,N)T[м]itthLс элементом, с независимой вероятностью 1 / 2 . Пусть p будет вероятностью, что σ произведен как продукция.(яT+1)sT1/2пσ

Я хотел бы знать (любой из) следующее:

  • Является ли решить N P -полная проблема?п>0Nп
  • Является ли вычисление точно # P -завершенным?п#п
  • Что мы можем сказать о приближении с точностью до мультипликативной константы? Есть ли для этого PTAS?п

Вариант, где обмены не должны быть из смежных элементов, также представляет интерес.

Обратите внимание, что нетрудно свести эту проблему к непересекающимся по краям путям (или к целочисленному многокомпонентному потоку); что я не знаю, так это сокращение в другом направлении.

Обновление: ОК, проверяя Garey & Johnson, их проблема [MS6] («Генерация перестановок») заключается в следующем. Учитывая в качестве входных данных целевую перестановку , вместе с подмножествами S 1 , , S m[ n ] , решить, можно ли выразить σ как произведение τ 1τ m , где каждое τ i действует тривиально на все индексы, не являющиеся в Си я . Garey, Джонсон, Миллер и Papadimitriou (за платный доступом, к сожалению) доказать , что эта проблема является NσSNS1,...,Sм[N]στ1τмτяSя хард.Nп

Если перестановки не должны быть смежными, то я считаю, что это означает, что решение о том, является ли также N P- трудным. Сокращение заключается просто в следующем: для каждого S 1 , S 2 , по порядку мы предложим набор «обменов-кандидатов», который соответствует полной сети сортировки на S i (т. Е. Способен произвольно переставлять S i , в то время как действует тривиально на все остальное). Тогда σ будет выражаться как τ 1τ m , если и только если оно достижимо как произведение этих перестановок.п>0NпS1,S2,...SяSяστ1τм

Это все еще оставляет открытой «оригинальную» версию (где перестановки имеют только смежные элементы). Для версии подсчета (с произвольными перестановками), конечно, настоятельно рекомендуется, чтобы проблема была -полной. В любом случае, это исключает PTAS , если P = N P .#ппзнак равноNп

Скотт Ааронсон
источник
1
Не уверен, что понимаю вопрос. Где вероятность? Вы меняете с вероятностью 1/2, а не с вероятностью 1/2?
Арнаб
@arnab да. Скотт, ты доказал это с , это все еще NP-сложный. Моя интуиция заключается в том, что ваша «оригинальная» проблема должна быть проще, но сначала я попробую поиграть с сокращением статьи. |Sя|знак равно2
didest

Ответы:

15

Я думаю, что можно ли решить p> 0 за полиномиальное время.

Рассматриваемая проблема может быть легко приведена в качестве задачи о непересекающихся ребрах, где базовый граф представляет собой плоский граф, состоящий из m + 1 слоев, каждый из которых содержит n вершин плюс m вершин степени 4 для представления возможных смежных перестановок. Обратите внимание, что планарность этого графа следует из того факта, что мы допускаем только смежные перестановки.

Если я не ошибаюсь, это относится к частному случаю задачи о непересекающихся путях, решаемой Окамурой и Сеймуром [OS81]. Кроме того, Вагнер и Вейхе [WW95] дают алгоритм линейного времени для этого случая.

См. Также лекционные заметки Геманса [Goe12], в которых дается хорошее изложение теоремы Окамуры – Сеймура и алгоритма Вагнера – Вейхе.

Ссылки

[Goe12] Мишель X. Гоманс. Конспект лекций, 18.438 Продвинутая комбинаторная оптимизация, лекция 23 . Массачусетский технологический институт, весна 2012 г. http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Харуко Окамура и Пол Д. Сеймур. Многокомпонентные потоки в плоских графах. Журнал комбинаторной теории, серия B , 31 (1): 75–81, август 1981 года. Http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Доротея Вагнер и Карстен Вейхе. Алгоритм линейного времени для непересекающихся по краям путей в плоских графах. Combinatorica , 15 (1): 135–150, март 1995 г. http://dx.doi.org/10.1007/BF01294465

Цуёси Ито
источник