Предположим, нам дана матрица n по n, M, с целочисленными элементами. Можем ли мы решить в P, существует ли перестановка такая, что для всех перестановок мы имеем ?
Замечания. Конечно, можно заменить продукт суммой, проблема остается той же.
Если матрица может иметь только 0/1 записей, то мы получаем проблему Bipartite-UPM, которая есть даже в NC.
Изменить: Решить, является ли наименьший член уникальным является трудным NP, если мы разрешаем рандомизированные сокращения. На самом деле, я изначально хотел поставить этот вопрос, потому что это помогло бы решить этот вопрос . Теперь выяснилось, что это NP-полная версия, поэтому позвольте мне вкратце описать проблему. Представьте, что входные данные представляют собой матрицу с нулем один (что мы можем предположить) и замените нулевые записи случайными действительными числами от 2 до 2 + 1 / n. Теперь в этой новой матрице с высокой вероятностью наименьший член уникален тогда и только тогда, когда исходная матрица переставляется в верхнетреугольную форму.
Изменить: Похожие вопросы:
В графе, взвешенном по ребрам, существует ли гамильтонов цикл с уникальным весом?
Если у нас есть CNF с весами, назначенными для каждой переменной / удовлетворяющего присвоения, существует ли уникальное назначение, удовлетворяющее весу?
Это, конечно, как минимум NP-жесткий. Эти проблемы эквивалентны оригиналу или они сложнее?
Ответы:
Хорошая проблема! Нетрудно дать сокращение, показывающее, что, если кто-то может решить вашу проблему, то можно также решить следующую проблему, назовите ее 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 к вашей проблеме следующим образом:
Теперь, ISOLATED SUBSET SUM, безусловно, чувствует, что он, по крайней мере, NP-жесткий, и, возможно, это даже сложнее, чем это (очевидная верхняя граница - только 2 P)! Кроме того, возможно, можно доказать, что ISOLATED SUBSET SUM является NP-трудной, используя рандомизированное сокращение в стиле Valiant-Vazirani. Это, однако, проблема, которую я оставляю кому-то еще ...
источник