Gibt es einen polynomiellen Zeitalgorithmus, um zu bestimmen, ob die Spanne einer Reihe von Matrizen eine Permutationsmatrix enthält?

Ich möchte einen polynomiellen Zeitalgorithmus finden, der bestimmt, ob die Spanne einer gegebenen Menge von Matrizen eine Permutationsmatrix enthält.

Wenn jemand weiß, ob dieses Problem von einer anderen Komplexitätsklasse ist, wäre das genauso hilfreich.

---

EDIT: Ich habe diese Frage mit Linear Programming markiert, weil ich den starken Verdacht habe, dass es sich bei einer solchen Lösung um eine Art linearen Programmieralgorithmus handelt. Ich glaube, das liegt daran, dass die Extrempunkte des Birkhoff-Polytops genau die Permutationsmatrizen sind. Wenn Sie dann eine objektive Funktion finden könnten, die entweder nur auf den Eckpunkten des Birkhoff-Polytops maximiert oder minimiert ist, könnten Sie Ihre Funktion auf den Schnittpunkt des Polytops und Ihres Vektor-Unterraums beschränken und dann in Polynomzeit maximieren. Wenn dieser Wert eine Permutationsmatrix wäre, würden Sie wissen, dass die Menge eine Permutation enthält. Das sind meine Gedanken zu diesem Thema.

---

EDIT 2: Nach einigem Nachdenken scheint es mir, dass die Permutationsmatrizen genau die Elemente des Birkhoff-Polytops mit euklidischer Norm sind $\sqrt{n}$ betrachten wir das Birkhoff-Polytop als die konvexe Hülle der$n \times n$Permutationsmatrizen. Vielleicht könnte das auch von Bedeutung sein.

---

EDIT 3: Ich habe das semidefinite Programmiertag hinzugefügt, da ich nach meinem vorherigen Kommentar anfange zu denken, dass eine semidefinite Programmierlösung möglich sein könnte, da es sich nun um einen linear beschränkten quadratischen Optimierungsalgorithmus handelt.

Satz. Das Problem in der Post ist NP-schwer, durch Reduktion von Subset-Sum.

Daraus folgt natürlich, dass es unwahrscheinlich ist, dass das Problem einen Poly-Time-Algorithmus hat, wie er von op angefordert wird.

---

Hier ist die Intuition. Das Problem in der Post ist

• Gibt es eine Permutationsmatrix in der Spanne eines gegebenen Satzes von Matrizen?

Dies ist im Wesentlichen dasselbe wie

• Gibt es eine Permutationsmatrix, die (wenn man die Matrix als Vektor betrachtet) einige gegebene lineare Bedingungen erfüllt?

Dies ist wiederum dasselbe wie

• Gibt es eine perfekte Übereinstimmung (in einem vollständigen zweigliedrigen Graphen), deren Inzidenzvektor einige gegebene lineare Bedingungen erfüllt?

Das Reduzieren von Subset-Sum auf das letztere Problem ist eine Standardübung.

Hier ist der ausführliche Beweis.

---

Definieren Sie das folgende Zwischenproblem:

Matching-Summe:

Eingabe: Complete, zweiteilige Graphen mit nicht-negativen ganzen Zahl Kantengewichten und nicht negativer ganzen Zahl Ziel T .$G=(U,V,E)$$T$

Ausgabe: Enthält eine perfekte Gewichtsanpassung genau T ?$G$$T$

---

Lemma 1 . Teilmengen-Summen-Polyzeit reduziert sich auf Matching-Sum.

Dies zu beweisen ist eine Standard-Hausaufgabe. Der Beweis ist am Ende.

Lemma 2. Matching-Sum Poly-Time reduziert sich auf das Problem in der Post.

Beweis von Lemma 2. Fixiere eine Matching-Sum-Eingabe: ein vollständiger zweigliedriger Graph mit nicht negativen ganzzahligen Kantengewichten w : U × V → N + und Ziel T ∈ N + , wobei U = { u 1 , … , u n } und V = { v 1 , … , v n } . Für jeden $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\}$ , definiere M ( i j ) als die Matrix in R ( n + 1 ) × ( n + 1 ), wobei M ( i j ) i j = T und M ( i j ) n + 1 , n + 1 = w ( $i,j\in\{1,2,\ldots,n\}$$M^{(ij)}$$\mathbb{R}^{(n+1)\times (n+1)}$$M^{(ij)}_{ij} = T$ und alle anderen Einträge sind Null. Die Reduktion gibt den folgenden Satz von Matrizen aus: { M ( i j ) : i , j ∈ { 1 , … , n } } . Dies definiert die Reduzierung.$M^{(ij)}_{n+1,n+1}=w(u_i, v_j)$

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

Anspruch. Die Spanne dieses Satzes von Matrizen besteht aus den Matrizen die die linearen Bedingungen M h , n + 1 = M n + 1 , h = 0 für alle h ≤ n und erfüllen die lineare Beschränkung $M \in\mathbb{R}^{(n+1)\times(n+1)}$$M_{h,n+1} = M_{n+1,h} = 0$$h\le n$

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

( Beweis des Anspruchs. Durch Inspektion erfüllt jede Matrix in der Menge diese Einschränkungen, so dass jede lineare Kombination dieser Matrizen dies tut. Umgekehrt, wenn M ∈ R ( n + 1 ) × ( n + 1 ) die Einschränkungen erfüllt , dann M gleich die Linearkombination M ' = Σ n i = 1 Σ N j = 1 α i j M ( i $M^{(ij)}$$M\in\mathbb{R}^{(n+1) \times (n+1)}$$M$ Der Matrizen, wobei α i j = M i j / M ( i j ) i j = M i j / T. Insbesondere Kenntnisdass durch die verschiedenen Definitionen und die linearen Constraints, M ' n + 1 , n + 1 = Σ i j α i j w ( u i , v j ) = Σ i j$M'=\sum_{i=1}^n \sum_{j=1}^n \alpha_{ij} M^{(ij)}$$\alpha_{ij} = M_{ij}/M^{(ij)}_{ij} = M_{ij}/T$ Dies beweist die Behauptung.)

$$\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}.$$

Jetzt zeigen wir, dass die Reduzierung korrekt ist. Das heißt, der gegebene Graph hat genau dann eine Übereinstimmung der Gewichtung T, wenn der Satz von Matrizen eine Permutationsmatrix überspannt.$G$$T$

( Nur wenn. ) Angenommen, der gegebene Graph hat ein Gewicht T, das perfekt zu M ' passt . Es sei M ∈ { 0 , 1 } ( n + 1 ) × ( n + 1 ) die entsprechende n × n- Permutationsmatrix, wobei eine zusätzliche Zeile und Spalte hinzugefügt wird, so dass M n + 1 , n + 1 = 1 und M h , n $G$$T$$M'$$M\in\{0,1\}^{(n+1)\times (n+1)}$$n\times n$$M_{n+1,n+1} = 1$für alleh≤n. Dann Σ n i = 1 Σ N j = 1 M i j w( u i , v j )ist das Gewicht von M ' , das heißt,Tund M n + 1 , n + 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$, Also die linearen Constraints im Anspruch halten, und die Spannweite des gegebenen Satzes von Matrizen enthalten die Permutationsmatrix .$M$

( Wenn. ) Umgekehrt wird angenommen, dass die Spanne eine Permutationsmatrix . Durch die Forderung, die nur Nicht-Null - Eintrag in der Zeile n + 1 oder Spalte n + 1 ist , M n + 1 , n + 1 , so (wie M eine Permutationsmatrix ist) muss es sein , daß M n + 1 , n + 1 = 1 . Wenn Sie also die letzte Zeile und Spalte löschen, erhalten Sie eine n × n- Permutationsmatrix. Sei M ' die perfekte Übereinstimmung von$M$$n+1$$n+1$$M_{n+1,n+1}$$M$$M_{n+1,n+1} = 1$$n\times n$$M'$ entsprechend dieser n × n Permutationsmatrix. Das Gewicht von M ' ist Σ n i = 1 Σ N j = 1 M i j w ( u i , v j ) , die (durch die Ansprüche) ist T M n + 1 , n + 1 = T . Das gegebene Diagramm hat also eine Gewichts- T- Übereinstimmung, was Lemma 2 beweist. 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$

Hier ist der verzögerte Beweis von Lemma 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\}$ is a solution to the given Subset-Sum instance (as these are the only non-zero weight edges in $M$).

Conversely, given any solution to the Subset-Sum instance, say $S\subseteq\{1,\ldots,n\}$ with $\sum_{i\in S} w_i = T$, the set of edges $\{(u_i, v_i) : i \in S\}$ is a partial matching with weight $T$, and it extends easily to a weight-$T$ perfect matching by adding, for example, the following set of (zero-weight) edges:

$$\{(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})\}.$$

This proves Lemma 1. The theorem follows from Lemmas 1 and 2. $~~~\Box$

---

p.s. As an aside, according to this answer, the restriction of Matching-Sum to instances with polynomially-bounded edge weights is in P. But I'm sure that the restriction of the problem in the post to matrices with polynomially-bounded (integer) entries remains NP hard.

Bezüglich des Problems der Berechnung des Durchmessers eines Polytops, das als Schnittpunkt von Halbräumen dargestellt wird, ist das Problem im Allgemeinen NP-hart und auch NP-hart, um sich innerhalb eines konstanten Faktors anzunähern, siehe Briedens Aufsatz und Referenzen darin. Ich denke für zentral symmetrische Polytope gibt ein SDP eine$O(\sqrt{\log m})$ Annäherung wo $m$ist die Anzahl der Ungleichungen, die das Polytop definieren. Ich skizziere das unter der Linie.

In Ihrem Fall das Birkhoff-Polytop $P$ ist nicht zentral symmetrisch, sondern arbeitet mit der konvexen Hülle von $P$ und $-P$genügt für Ihre Zwecke. Ich denke, dieses "symmetrische Birkhoff" -Polytop kann als die Menge aller quadratischen Matrizen dargestellt werden$M$ die erfüllen:

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

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

$$-1 \leq c \leq 1$$

Wenn dies eine korrekte Darstellung ist (nicht sicher), können Sie einfach die Einschränkungen hinzufügen, die dieses Polytop auf den angegebenen Unterraum beschränken. Es ist nicht schwer, das SDP unter dem Strich an diese Darstellung anzupassen, aber ich entscheide mich, es nicht durchzugehen, um die Notation handhabbar zu halten.

Ich bin nicht sicher, was der ungefähre Durchmesser für Ihr Problem bedeutet: Sie können wahrscheinlich entscheiden, ob sich der angegebene Unterraum in der Nähe einer Permutationsmatrix oder weit entfernt von allen befindet, aber ich habe die Berechnungen nicht ausgearbeitet.

---

Lassen Sie mich mit einer Skizze der SDP-Rundung abschließen (die ziemlich normal ist). Lassen$P = \{x: -b \leq Ax \leq b\}$ ein zentral symmetrisches Polytop sein, wo $A$ ist $m \times n$. Definieren Sie das Vektorprogramm:

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

unterliegen:

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

Über $v_i$ reichen über $n$Vektoren. Dies kann standardmäßig als SDP geschrieben werden und ist eine Entspannung des Durchmessers von$P$dh $\alpha$ ist mindestens der euklidische Durchmesser von $P$.

Das behaupte ich jetzt $\alpha \leq O(\sqrt{\log m})\cdot \text{diam}(P)$. Um dies zu zeigen, werde ich Ihnen einen Algorithmus geben, der gegeben ist$(v_i)_{i=1}^n$ von Wert $\alpha$Ausgänge $x \in P$ der Länge mindestens $\frac{\alpha}{O(\sqrt{\log m})}$. Der Algorithmus ist nur eine zufällige Projektion: Wählen Sie eine zufällige$n$Vektor $g$ wo jeder $g_i$ist ein Standard-Gaußscher. einstellen$\tilde{x}_i = g^T v_i$. Durch Standardeigenschaften von Gaußschen:

$$\mathbb{E}\ \|\tilde{x}\|_2^2 = \alpha^2$$ $$\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}.$$ wo die letzte Schranke groß genug ist $C$ (Dies ist eine Standardtatsache über das Maximum von $m$ subguassianische Zufallsvariablen und kann mit der Chernoff-Grenze bewiesen werden).

Die beiden Gleichungen implizieren bereits, dass eine existiert $x$ so dass $x \in P$ und $\|x\|_2^2 \geq \frac{1}{C\sqrt{\log m}}\alpha$. Oder Sie können dies mithilfe von Konzentrationsgrenzen mit konstanter Wahrscheinlichkeit zeigen$\frac{1}{2C\sqrt{\log m}}\tilde{x} \in P$ und $\|\tilde{x}\|_2\geq \frac{1}{2}\alpha$.