Questions marquées «permanent»

Compter le nombre de correspondances parfaites dans un graphe bipartite est immédiatement réductible au calcul du permanent. Étant donné que trouver une correspondance parfaite dans un graphique non bipartite est dans NP, il existe une certaine réduction des graphiques non bipartites au permanent,...

À la lumière du récent abîme à la profondeur-3 (qui donne entre autres un circuit arithmétique de profondeur profondeur 3 pour le déterminant sur ), J'ai les questions suivantes: Grigoriev et Karpinski ont prouvé une limite inférieure de pour tout circuit arithmétique de profondeur 3 calculant le...

1- Existe-t-il des propriétés spécifiques pour la matrice d'adjacence lorsqu'un graphe est plan? 2- Y a-t-il quelque chose de spécial pour calculer la matrice permanente d'adjacence lorsqu'un graphe est

Wikipedia fournit des exemples de problèmes où la version de comptage est difficile, alors que la version de décision est facile. Certains d'entre eux comptent des appariements parfaits, comptant le nombre de solutions à 222 -SAT et le nombre de tri topologiques. Existe-t-il d'autres classes...

Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...

Supposons que l'on nous donne une matrice n par n, M, avec des entrées entières. Peut-on décider dans P s'il existe une permutation telle que pour toutes les permutations π ≠ σ on a Π M i σ ( i ) ≠ Π M i π ( i ) ?σσ\sigmaπ≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Π Mi π( i )ΠMjeσ(je)≠ΠMjeπ(je)\Pi...

Ceci fait suite à cette question et est lié à cette question de Shiva Kinali. Il semble que les preuves dans ces articles ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) utilisent des théorèmes de hiérarchie. Je veux savoir si les preuves sont des théorèmes de diagonalisation "...

Dans l'article de Ben-Dor / Halevi [1], il est donné une autre preuve que le permanent est #P#P\#P complet. Dans la dernière partie de l'article, ils montrent la chaîne de réduction IntPerm∝NoNegPerm∝2PowersPerm∝0/1-PermIntPerm∝NoNegPerm∝2PowersPerm∝0/1-Perm\begin{equation} \text{IntPerm} \propto...

Un problème majeur du TCS est le problème de l'expression d'un permanent comme déterminant. Je lisais le document d'Agrawal Determinant Versus Permanent et dans un paragraphe, il affirme que le problème inverse est facile. Il est facile de voir que le déterminant d'une matrice peut être exprimé...

Considérons le problème suivant: étant donné une matrice , les indices i, j \ in \ {1, \ dots, n \ } et un entier a . Remplacer M [i, j] par une et appeler nouvelle matrice \ M chapeau . Est-ce que par (M)> par (\ chapeau M) ? i , j ∈ { 1 , ... , n } a M [ i , j ] une M p e r ( M ) > p e r (...

AAA3×33×33 \times 34×44×44 \times 4aijaija_{ij}BBBper(A)=det(B)per⁡(A)=det(B)\operatorname{per}(A) = \det(B)BBBper(A)=det(B)per⁡(A)=det(B)\operatorname{per}(A) = \det(B) Certaines restrictions pourraient être les cas suivants: Cas Seuls sont autorisés linéaire Fonctionnelles sous forme d' entrées...

L'algorithme de Berkowitz fournit un circuit de taille polynomiale avec une profondeur logarithmique pour déterminer une matrice carrée en utilisant des puissances matricielles. L'algorithme utilise implicitement l'annulation. L'annulation est-elle essentielle pour atteindre un circuit de taille...