Существует ли алгоритм полиномиального времени, чтобы определить, содержит ли диапазон набора матриц матрицу перестановок?

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

Если кто-нибудь знает, относится ли эта проблема к другому классу сложности, это было бы так же полезно.

РЕДАКТИРОВАТЬ: я пометил этот вопрос с помощью линейного программирования, потому что у меня есть сильное подозрение, что если бы такое решение существовало, это был бы своего рода алгоритм линейного программирования. Я полагаю, что причина в том, что крайние точки многогранника Биркгофа - это именно матрицы перестановок. Если бы тогда вы могли найти целевую функцию, которая максимизируется или минимизируется только на вершинах многогранника Биркгофа, вы можете ограничить свою функцию пересечением многогранника и вашего векторного подпространства, а затем максимизировать ее за полиномиальное время. Если бы это значение было матрицей перестановок, вы бы знали, что набор содержит перестановку. Это мои мысли на эту тему.

РЕДАКТИРОВАТЬ 2: После некоторого дополнительного размышления, мне кажется, что матрицы перестановок являются точно элементами многогранника Биркгофа с евклидовой нормой $\sqrt{n}$ , мы считаем многогранник Биркгофа выпуклой оболочкойматриц перестановок $n \times n$ . Возможно, это также может быть значительным.

РЕДАКТИРОВАТЬ 3: Я добавил полуопределенный тег программирования, потому что после моего предыдущего комментария я начинаю думать, что полуопределенное программирование может быть возможным, поскольку теперь это алгоритм линейной зависимости квадратичной оптимизации.

cc.complexity-theory linear-algebra linear-programming semidefinite-programming polynomial-time Ник
источник

Какой тип записей будет иметь входные матрицы?

$\;$

Записи могут быть в любом поле, есть некоторая свобода в настройке матриц; однако вам нужно достаточно большое поле (поэтому поле характеристики 2, например, не годится).

Ник

Можете объяснить, каков размер набора матриц?

Мухаммед Аль-Туркистани

Мухаммед: Я думаю, что это линейная комбинация множества матриц.

Вивек Багария

@DavidRicherby Я думаю, что путаница Мохаммеда связана с тем фактом, что обычно мы думаем о матрицах как о представлении линейных карт, а диапазон линейных карт иногда используется в качестве другого термина для его диапазона. Но это не имеет смысла, поэтому я думаю, что мы должны думать о матрицах как о элементах векторного пространства

Сашо Николов

Ответы:

Теорема. Проблема в посте - NP-сложная, за счет сокращения от Subset-Sum.

Конечно, из этого следует, что проблема вряд ли будет иметь многовременный алгоритм, как того требует op.

Вот эта интуиция. Проблема в посте

Существует ли матрица перестановок в диапазоне заданного набора матриц?

Это по сути так же, как

Существует ли матрица перестановок, которая (рассматривая матрицу как вектор) удовлетворяет некоторым заданным линейным ограничениям?

Это в свою очередь так же, как

Существует ли идеальное совпадение (в полном двудольном графе), вектор инцидентности которого удовлетворяет некоторым заданным линейным ограничениям?

Сокращение Subset-Sum до последней проблемы является стандартным упражнением.

Вот подробное доказательство.

Определите следующую промежуточную задачу:

Соответствие-Sum:

вход: полный двудольный граф с неотрицательными весами ребер целого числа, и неотрицательной целое числом целевой . $G=(U,V,E)$ $T$

Вывод: содержит ли точное совпадение веса точно ? $G$ $T$

Лемма 1 . Полумесяц Subset-Sum сводится к Matching-Sum.

Доказательство это стандартное домашнее задание. Доказательство в конце.

Лемма 2. Сопоставление-сумма множителей сводится к проблеме в посте.

Доказательство леммы 2. Зафиксируем входную сумму совпадения: полный двудольный граф с неотрицательными целочисленными ребрами веса и целью , где и . Для каждого $G=(U,V,E)$ $w:U\times V\rightarrow \mathbb{N}_+$ $T\in \mathbb{N}_+$ $U=\{u_1,\ldots,u_n\}$ $V=\{v_1, \ldots, v_n\}$ , определите как матрицу в где и , а все остальные записи равны нулю. Сокращение выводит следующий набор матриц: $i,j\in\{1,2,\ldots,n\}$ $M^{(ij)}$ $\mathbb{R}^{(n+1)\times (n+1)}$ $M^{(ij)}_{ij} = T$ $M^{(ij)}_{n+1,n+1}=w(u_i, v_j)$ Это определяет сокращение.

{M^{(i j)} : i, j \in {1, \dots, n}} .

$\big\{M^{(ij)} : i,j\in\{1,\ldots,n\}\big\}.$

Запрос. Оболочка этого набора матриц состоит из этих матриц удовлетворяют линейным ограничениямдля всехи линейное ограничение $M \in\mathbb{R}^{(n+1)\times(n+1)}$ $M_{h,n+1} = M_{n+1,h} = 0$ $h\le n$

\sum_{i = 1}^{n} \sum_{j = 1}^{n} M_{i j} w (u_{i}, v_{j}) = T M_{n + 1, n + 1} .

$\textstyle\sum_{i=1}^n\sum_{j=1}^n M_{ij}\,w(u_i, v_j) = T\, M_{n+1,n+1}.$

( Доказательство утверждения. При проверке каждой матрицы в наборе удовлетворяет этим ограничениям, поэтому каждая линейная комбинация этих матриц удовлетворяет. И наоборот, если удовлетворяет ограничениям тогдаравно линейной комбинации $M^{(ij)}$ $M\in\mathbb{R}^{(n+1) \times (n+1)}$ $M$ из матриц, где $M'=\sum_{i=1}^n \sum_{j=1}^n \alpha_{ij} M^{(ij)}$ . Обратите вниманиечтов частности,помощью различных определений и линейных ограничений, $\alpha_{ij} = M_{ij}/M^{(ij)}_{ij} = M_{ij}/T$ Это доказывает иск.)

M_{n + 1, n + 1}^{'} = \sum_{i j} α_{i j} w (u_{i}, v_{j}) = \sum_{i j} M_{i j} w (u_{i}, v_{j}) / T = (T M_{n + 1, n + 1}) / T = M_{n + 1, n + 1} .

$\textstyle M'_{n+1,n+1} = \sum_{ij} \alpha_{ij} w(u_i, v_j) = \sum_{ij} M_{ij} w(u_i, v_j)/T = (T\, M_{n+1,n+1})/T = M_{n+1,n+1}.$

Теперь мы показываем, что сокращение является правильным. То есть данный граф имеет вес- совпадающий тогда и только тогда, когда набор матриц охватывает матрицу перестановок. $G$ $T$

( Только если. ) Сначала предположим, что данный граф для всех . Тогда есть весовое идеальное соответствие . Пусть - соответствующаяматрица перестановок с добавлением дополнительной строки и столбца, так что $G$ $T$ $M'$ $M\in\{0,1\}^{(n+1)\times (n+1)}$ $n\times n$ $M_{n+1,n+1} = 1$ и $M_{h,n+1}=M_{n+1,h}=0$ $h\le n$ является вес, то есть,и $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ $M'$ $T$ $M_{n+1,n+1}=1$ , Так что линейные ограничения в трюме претензии, и продолжительность данного набора матриц перестановок содержат матрицу . $M$

( Матрица перестановок. Масса является Если. ) С другой стороны , предположим , что оболочка содержит любую перестановку матрицу . Согласно утверждению, единственная ненулевая запись в строке или столбце - это , поэтому (поскольку является матрицей перестановок), должно быть, что . Таким образом, удаление последней строки и столбца дает матрицу перестановок . Пусть будет идеальным соответствием $M$ $n+1$ $n+1$ $M_{n+1,n+1}$ $M$ $M_{n+1,n+1} = 1$ $n\times n$ $M'$ соответствует этой , который (по п) является . Таким образом, данный граф имеет соответствие веса и , что доказывает лемму 2. $G$ $n\times n$ $M'$ $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ $T M_{n+1,n+1} = T$ $T$ $~~\Box$

Вот отложенное доказательство леммы 1:

Доказательство леммы 1. Для данного экземпляра суммы подмножеств редукция выдает экземпляр суммы совпадений где , $(w,T)\in\mathbb{N}^n_+ \times \mathbb{N}_+$ $(G=(U,V,E), T)$ $U=\{u_1, u_2, \ldots, u_{2n}\}$ имеет вес , а все остальные ребра имеют вес ноль. , для каждого , ребра $V=\{v_1, v_2, \ldots, v_{2n}\}$ $i\in\{1,\ldots,n\}$ $(u_i, v_i)$ $w_i$

Для любого идеального соответствия с весами ребер, суммирующими с , множество является решением данного экземпляра суммы подмножества (так как они являются единственными ребра с нулевым весом в ). $T$ $S=\{i : (u_i, v_i)\in M, i\le n\}$ $M$

Наоборот, при любом решении экземпляра суммы подмножеств, скажем, с , множество ребер равно частичное сопоставление с весом , и оно легко распространяется на идеальное сопоставление веса путем добавления, например, следующего набора ребер (с нулевым весом): $S\subseteq\{1,\ldots,n\}$ $\sum_{i\in S} w_i = T$ $\{(u_i, v_i) : i \in S\}$ $T$ $T$

{(u_{i + n}, v_{i + n}) : i \in S} \cup ⋃_{i \in {1, \dots, n} ∖ S} {(u_{i}, v_{i + n}), (u_{i + n}, v_{i})} .

$\{(u_{i+n}, v_{i+n}) : i\in S\} \cup \bigcup_{i\in\{1,\ldots,n\}\setminus S}\{(u_i, v_{i+n}), (u_{i+n}, v_{i})\}.$

Это доказывает лемму 1. Теорема следует из лемм 1 и 2. $~~~\Box$

ps Кроме того, согласно этому ответу , ограничение Matching-Sum на экземпляры с полиномиально ограниченными весами ребер находится в P. Но я уверен, что ограничение задачи в посте на матрицы с полиномиально-ограниченными (целое число ) записи остается нп хард.

Нил Янг
источник

Похоже, вы берете выпуклый корпус матриц, а не пролет. Диапазон матриц, которые вы описали, является полным пространством матриц. Или я что-то упустил?

Ванесса

@ Squark, вы правы - я неверно истолковал «span». Спасибо. Я исправил доказательство, чтобы использовать правильное определение диапазона (как любой линейной комбинации матриц).

Нил Янг,

Ницца! Я думаю, что было бы лучше умножить определение

на

, чтобы нам не приходилось делить на что-то, что может быть 0? Кроме того, кажется, что доказательство может быть несколько упрощено путем объединения двух сокращений без промежуточной проблемы.

M^{(i j)}

$M^{(ij)}$

w (u_{i}, v_{j})

$w(u_i,v_j)$

Ванесса

Хороший момент о делении на ноль. Я исправлю это. Я оставлю два сокращения отдельно, хотя для меня это более интуитивно понятно.

Нил Янг

Относительно проблемы вычисления диаметра многогранника, представленного как пересечение полупространств, проблема является NP-трудной в целом, а также NP-трудной для аппроксимации в пределах любого постоянного множителя, см. Статью Бридена и ссылки в ней. Я думаю, что для центрально-симметричных многогранников SDP дает приближение, где- число неравенств, определяющих многогранник. Я рисую это ниже черты. $O(\sqrt{\log m})$ $m$

В вашем случае многогранник Биркгофа не является центрально-симметричным, но для ваших целей достаточно работы с выпуклой оболочкой и Я думаю, что этот «симметричный многогранник Биркгофа» можно представить как множество всех квадратных матриц $P$ $P$ $-P$ $M$ которые удовлетворяют:

\forall я^{*}, J^{*} : \underset{я}{Σ} M_{я J^{*}} знак равно \underset{J}{Σ} M_{я^{*} J} знак равно с

$\forall i^*, j^*: \sum_{i}{M_{ij^*}} = \sum_j{M_{i^*j}} = c$

\forall я, J : - 1 \leq M_{я J} \leq 1

$\forall i,j: -1 \leq M_{ij} \leq 1$

- 1 \leq с \leq 1

$-1 \leq c \leq 1$

Если это правильное представление (не уверен), то вы можете просто добавить ограничения, которые ограничивают этот многогранник для вашего данного подпространства. Нетрудно адаптировать SDP под линией к этому представлению, но я предпочитаю не проходить его, чтобы сохранить нотацию управляемой.

Я не уверен, что приблизительный диаметр делает для вашей задачи: он, вероятно, позволяет вам решить, является ли данное подпространство близко к матрице перестановок или далеко от всех из них, но я не разработал расчеты.

Позвольте мне закончить с эскизом округления SDP (который является довольно стандартным тарифом). Пусть - центрально-симметричный многогранник, где - . Определим векторную программу: $P = \{x: -b \leq Ax \leq b\}$ $A$ $m \times n$

$\alpha^2 = \max \sum_{i = 1}^n{\|v_i\|_2^2}$

при условии:

$\forall 1 \leq i \leq m: \|\sum_{j = 1}^n{A_{ij} v_j}\|_2^2 \leq b_i^2$

$v_i$ $n$ $P$ $\alpha$ $P$ .

. Чтобы показать это, я дам вам алгоритм, который, учитывая $\alpha \leq O(\sqrt{\log m})\cdot \text{diam}(P)$ $(v_i)_{i=1}^n$ $\alpha$ $x \in P$ $\frac{\alpha}{O(\sqrt{\log m})}$ $n$ $g$ $g_i$ $\tilde{x}_i = g^T v_i$

E ‖ \tilde{x} ‖_{2}^{2} = α^{2}

$\mathbb{E}\ \|\tilde{x}\|_2^2 = \alpha^2$

\forall i \leq m : E | (A \tilde{x})_{i} |^{2} \leq b_{i}^{2} \Rightarrow E {max}_{i = 1}^{m} \frac{| (A \tilde{x})_{i} |}{b_{i}} \leq C \sqrt{\log m} .

$\forall i \leq m: \mathbb{E}\ |(A\tilde{x})_i|^2 \leq b_i^2 \ \ \Rightarrow \ \ \mathbb{E}\ \max_{i=1}^m{\frac{|(A\tilde{x})_i|}{b_i}} \leq C\sqrt{\log m}.$

C

$C$

m

$m$ субгуасовых случайных величин и может быть доказан с использованием границы Черноффа).

$x$ $x \in P$ $\|x\|_2^2 \geq \frac{1}{C\sqrt{\log m}}\alpha$ $\frac{1}{2C\sqrt{\log m}}\tilde{x} \in P$ $\|\tilde{x}\|_2\geq \frac{1}{2}\alpha$ .

Sasho Nikolov
источник