Можем ли мы решить, есть ли у перманента уникальный термин?

16

Предположим, нам дана матрица n по n, M, с целочисленными элементами. Можем ли мы решить в P, существует ли перестановка такая, что для всех перестановок мы имеем ?σπσΠMяσ(я)ΠMяπ(я)

Замечания. Конечно, можно заменить продукт суммой, проблема остается той же.

Если матрица может иметь только 0/1 записей, то мы получаем проблему Bipartite-UPM, которая есть даже в NC.

Изменить: Решить, является ли наименьший член уникальным является трудным NP, если мы разрешаем рандомизированные сокращения. На самом деле, я изначально хотел поставить этот вопрос, потому что это помогло бы решить этот вопрос . Теперь выяснилось, что это NP-полная версия, поэтому позвольте мне вкратце описать проблему. Представьте, что входные данные представляют собой матрицу с нулем один (что мы можем предположить) и замените нулевые записи случайными действительными числами от 2 до 2 + 1 / n. Теперь в этой новой матрице с высокой вероятностью наименьший член уникален тогда и только тогда, когда исходная матрица переставляется в верхнетреугольную форму.

Изменить: Похожие вопросы:

В графе, взвешенном по ребрам, существует ли гамильтонов цикл с уникальным весом?

Если у нас есть CNF с весами, назначенными для каждой переменной / удовлетворяющего присвоения, существует ли уникальное назначение, удовлетворяющее весу?

Это, конечно, как минимум NP-жесткий. Эти проблемы эквивалентны оригиналу или они сложнее?

domotorp
источник
Знаем ли мы, есть ли эта проблема даже в NP? У меня трудности с получением сертификата.
Чт
Σ2п

Ответы:

13

Хорошая проблема! Нетрудно дать сокращение, показывающее, что, если кто-то может решить вашу проблему, то можно также решить следующую проблему, назовите ее ISOLATED SUBSET SUM:

Даны целые числа a 1 , ..., a n , есть ли подмножество S из a i i , сумма которых не разделена никаким другим подмножеством?

Сокращение работает, сначала сводя ИЗОЛИРОВАННУЮ СУММУ ПОДПИСИ к ИЗОЛИРОВАННОМУ ИДЕАЛЬНОМУ СОЧЕТАНИЮ, где с учетом взвешенного двудольного графа G мы хотим найти идеальное соответствие, вес которого не разделяется никаким другим идеальным соответствием. Это сокращение простое: для каждого i создайте полный подграф G i в G, равный 2x2 , так, чтобы любое из двух возможных совпадений, которые мы выбираем для G i, кодировало наш выбор, находится ли a i в множестве S.

Затем, уменьшите ISOLATED PERFECT MATCHING к вашей проблеме следующим образом:

  1. Для всех i, j, если ребро (i, j) существует и имеет вес w ij , то задайте M ij : = exp (w ij ). (Это превращает суммы в продукты.)
  2. Для всех i, j, если ребро (i, j) не существует, тогда установите M ij : = 0.
  3. Дополните M, чтобы убедиться, что есть две или более перестановок π, таких что ΠM i, π (i) = 0. (Это исключает ложные решения, которые не соответствуют никакому идеальному совпадению в G.)

Теперь, ISOLATED SUBSET SUM, безусловно, чувствует, что он, по крайней мере, NP-жесткий, и, возможно, это даже сложнее, чем это (очевидная верхняя граница - только 2 P)! Кроме того, возможно, можно доказать, что ISOLATED SUBSET SUM является NP-трудной, используя рандомизированное сокращение в стиле Valiant-Vazirani. Это, однако, проблема, которую я оставляю кому-то еще ...

Скотт Ааронсон
источник
Да, это эквивалентно. Фактически, если вы проверите открытую проблему, которую я пытаюсь решить, вы увидите, что я исхожу из проблемы ИЗОЛИРОВАННОГО ИДЕАЛЬНОГО СОГЛАСОВАНИЯ. Может быть, можно найти сокращение к / из проблемы монеты Фробениуса.
Домоторп
4
Даааа ... Энди Друкер с готовностью указал, что мою проблему ИЗОЛИРОВАННОЙ СУБСЕТНОЙ СУММЫ тривиально решить! Если некоторые из a_i равны 0, то уникальной суммы нет; в противном случае возьмите набор всех a_i, имеющих один и тот же знак (положительный или отрицательный). Итак, мы должны сосредоточиться на ИЗОЛИРОВАННОЕ ИДЕАЛЬНОЕ СОВМЕСТНОЕ.
Скотт Ааронсон