Я заинтересован в следующей проблеме. В качестве входных данных нам дается «целевая перестановка» , а также упорядоченный список индексов i 1 , … , i m ∈ [ n - 1 ] . Затем, начиная со списка L = ( 1 , 2 , … , n ) (т. Е. Перестановки тождеств), на каждом временном шаге t ∈ [ m ] мы меняем элемент i t h t в Lс элементом, с независимой вероятностью 1 / 2 . Пусть p будет вероятностью, что σ произведен как продукция.
Я хотел бы знать (любой из) следующее:
- Является ли решить N P -полная проблема?
- Является ли вычисление точно # P -завершенным?
- Что мы можем сказать о приближении с точностью до мультипликативной константы? Есть ли для этого PTAS?
Вариант, где обмены не должны быть из смежных элементов, также представляет интерес.
Обратите внимание, что нетрудно свести эту проблему к непересекающимся по краям путям (или к целочисленному многокомпонентному потоку); что я не знаю, так это сокращение в другом направлении.
Обновление: ОК, проверяя Garey & Johnson, их проблема [MS6] («Генерация перестановок») заключается в следующем. Учитывая в качестве входных данных целевую перестановку , вместе с подмножествами S 1 , … , S m ∈ [ n ] , решить, можно ли выразить σ как произведение τ 1 ⋯ τ m , где каждое τ i действует тривиально на все индексы, не являющиеся в Си я . Garey, Джонсон, Миллер и Papadimitriou (за платный доступом, к сожалению) доказать , что эта проблема является N хард.
Если перестановки не должны быть смежными, то я считаю, что это означает, что решение о том, является ли также N P- трудным. Сокращение заключается просто в следующем: для каждого S 1 , S 2 , … по порядку мы предложим набор «обменов-кандидатов», который соответствует полной сети сортировки на S i (т. Е. Способен произвольно переставлять S i , в то время как действует тривиально на все остальное). Тогда σ будет выражаться как τ 1 ⋯ τ m , если и только если оно достижимо как произведение этих перестановок.
Это все еще оставляет открытой «оригинальную» версию (где перестановки имеют только смежные элементы). Для версии подсчета (с произвольными перестановками), конечно, настоятельно рекомендуется, чтобы проблема была -полной. В любом случае, это исключает PTAS , если P = N P .
источник
Ответы:
Я думаю, что можно ли решить 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
источник