Als «permanent» getaggte Fragen

Das Zählen der Anzahl perfekter Übereinstimmungen in einem zweigeteilten Graphen ist sofort auf die Berechnung der bleibenden Karte reduzierbar. Da sich das Finden einer perfekten Übereinstimmung in einem nicht bipartiten Graphen in NP befindet, gibt es eine gewisse Reduktion von nicht bipartiten...

In Anbetracht der jüngsten Kluft bei Tiefe-3 ergibt sich (was unter anderem eine Tiefen-3-Arithmetikschaltung für die Determinante über ergibt ), Ich habe folgende Fragen: Grigoriev und Karpinski haben eine Untergrenze für jede arithmetische Tiefen-3-Schaltung bewiesen, die die Determinante von...

1- Gibt es spezielle Eigenschaften für die Adjazenzmatrix, wenn ein Diagramm planar ist? 2- Gibt es etwas Besonderes für die Berechnung der permanenten Adjazenzmatrix, wenn ein Graph planar

Wikipedia bietet Beispiele für Probleme, bei denen die Zählversion schwierig ist, während die Entscheidungsversion einfach ist. Einige von diesen zählen perfekte Übereinstimmungen, zählen die Anzahl der Lösungen zu SAT und die Anzahl der topologischen Sortierungen.222 Gibt es noch andere wichtige...

Ist es möglich, algorithmisch zu testen, ob eine berechenbare Zahl rational oder ganzzahlig ist? Mit anderen Worten, könnte eine Bibliothek, die berechenbare Zahlen implementiert, die Funktionen bereitstellen, isIntegeroder isRational? Ich vermute, dass es nicht möglich ist und dass dies irgendwie...

Angenommen, wir erhalten eine nxn-Matrix M mit ganzzahligen Einträgen. Können wir in P entscheiden, ob es eine Permutation so dass wir für alle Permutationen ?σσ\sigmaπ≠σπ≠σ\pi\ne\sigmaΠMiσ(i)≠ΠMiπ( i )ΠMiσ(i)≠ΠMichπ(ich)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Bemerkungen. Man kann das Produkt...

Dies ist eine Antwort auf diese Frage und steht im Zusammenhang mit dieser Frage von Shiva Kinali. Es scheint, dass die Beweise in diesen Arbeiten ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) Hierarchiesätze verwenden. Ich möchte wissen, ob es sich bei den Beweisen um " reine...

In der Arbeit von Ben-Dor / Halevi [1] wird ein weiterer Beweis dafür erbracht, dass die bleibende Karte #P-vollständig ist. Im späteren Teil der Arbeit wird die Reduktionskette während der permanente Wert in der Kette erhalten bleibt. Da sich die Anzahl der zufriedenen Zuordnungen einer...

Ein Hauptproblem bei TCS ist das Problem, eine bleibende Karte als Determinante auszudrücken. Ich habe Agrawals Artikel Determinant Versus Permanent gelesen und in einem Absatz behauptet er, das umgekehrte Problem sei einfach. Es ist leicht zu erkennen, dass die Determinante einer Matrix als die...

Betrachten Sie das folgende Problem: gegeben eine Matrix , Indizes i , j ∈ { 1 , … , n } und eine ganze Zahl a . Ersetzen M [ i , j ] durch eine neue Matrix nennen M . Ist p e r ( M ) > pM∈{−m,…,0,…,m}n×nM∈{−m,…,0,…,m}n×nM\in\{-m,\dots,0,\dots,m\}^{n\times...

Sei AAA eine 3 × 33×33 \times 3 oder eine 4 × 44×44 \times 4 Matrix mit Einträgen eini jaija_{ij} . Kann mir jemand eine Matrix B.BB so dass pro( A ) = det ( B )per⁡(A)=det(B)\operatorname{per}(A) = \det(B) ? Was ist das kleinste explizite B.BB , das bekannt ist, so dass pro( A ) = det ( B...

Der Berkowitz-Algorithmus liefert eine Polynomgrößenschaltung mit logarithmischer Tiefe zur Determinante einer quadratischen Matrix unter Verwendung von Matrixleistungen. Der Algorithmus verwendet implizit die Löschung. Ist eine Aufhebung wesentlich, um eine Schaltung mit Polynomgröße mit...

Sei eine gegebene quadratische Matrix. Gibt es Hinweise darauf, dass es schwierig sein könnte, quadratische Untergrenzen für B zu schlagen, so dass det ( B ) = per ( A ) schwierig sein könnte?AAABBBdet(B)=per(A)det(B)=per(A)\text{det}(B) = \text{per}(A) Gibt es eine plausible Vermutung, die...

In [1] heißt es: „Es bleibt eine offene Frage, ob jede Funktion in hat T C 0 Schaltungen (obwohl es ist zumindest bekannt , dass nicht alle # P Funktionen haben DLogTime förmige T C 0 Schaltungen).“# P.#P\#PT.C.0TC0TC^0# P.#P\#PT.C.0TC0TC^0 Schaltungen erzeugt durch DLogTime Funktionen nicht...