On prétend parfois que la théorie de la complexité géométrique de Ketan Mulmuley est le seul programme plausible pour régler les questions en suspens de la théorie de la complexité, comme la question P vs NP. Plusieurs théoriciens de la complexité connus ont commenté positivement le programme....
Autant que je sache, le programme de théorie de la complexité géométrique tente de séparer en prouvant que le permament d'une matrice à valeurs complexes est beaucoup plus difficile à calculer que le déterminant.VP≠VNPVP≠VNPVP \neq VNP Après avoir parcouru les documents du GCT, la question que je...
En général, nous savons qu'il est plus facile de tester si une fonction prend une valeur particulière à une entrée donnée que d'évaluer la fonction à cette entrée. Par exemple: L'évaluation du permanent d'une matrice de nombre entier non négatif est # P-difficile, mais indiquer si un tel permanent...
SoitAAA un entier positif fixe de taille nnn bits. On est autorisé à prétraiter cet entier comme il convient. Etant donné un autre entier positif BBB de taille mmm bits, quelle est la complexité de la multiplication ABABAB ?
Récemment, j'ai vu plusieurs articles sur arxiv qui se réfèrent à un système de preuve appelé somme des carrés. Quelqu'un peut-il expliquer ce qu'est une preuve de somme des carrés et pourquoi ces preuves sont importantes / intéressantes? Comment sont-ils liés à d'autres systèmes de preuve...
La théorie des catégories et l'algèbre abstraite traitent de la façon dont les fonctions peuvent être combinées avec d'autres fonctions. La théorie de la complexité traite de la difficulté de calculer une fonction. C'est bizarre pour moi que je n'ai vu personne combiner ces domaines d'études, car...
En lisant un article sur l'utilisation de méthodes algébriques pour détecter certains sous-graphes induits, il apparaît que l' idéal de bord est un outil important reliant l'algèbre commutative et la théorie des graphes. Comme je ne suis pas familier avec les calculs d'objets algébriques,...
Cette question peut être posée soit dans le cadre de la complexité des circuits des circuits booléens, soit dans le cadre de la théorie de la complexité algébrique, soit probablement dans de nombreux autres contextes. Il est facile de montrer, en comptant les arguments, qu'il existe des fonctions...
De nombreux cryptosystèmes à clé publique ont une sorte de sécurité prouvable. Par exemple, le cryptosystème Rabin est aussi difficile que l'affacturage. Je me demande si ce type de sécurité prouvable existe pour les cryptosystèmes à clé secrète, tels que AES. Sinon, quelle est la preuve qu'il est...
Je veux en savoir plus sur les algorithmes algébriques et la complexité de la théorie. Je m'intéresse en particulier au PIT. Existe-t-il un ensemble de notes de cours, de livres, d'articles et d'enquêtes pour les étudiants qui ont lu un manuel standard sur la théorie comme le livre de Sipser ou le...
Comme dans cette question, je suis intéressé par le problème vs / pour les circuits tropicaux et (\ min, +) . Cette question se réduit à montrer les limites supérieures de la dimension VC des polynômes sur les semirings tropicaux (voir le théorème 2 ci-dessous).
Dans leur article fondateur Algorithmes théoriques de groupe pour les multiplications matricielles , Cohn, Kleinberg, Szegedy et Umans introduisent le concept de puzzle résolvable de manière unique (défini ci-dessous) et de capacité USP. Ils affirment que Chaudronnier et Winograd, dans leur propre...
L'élimination gaussienne rend le déterminant d'une matrice polynomiale temps calculable. La réduction de la complexité dans le calcul du déterminant, qui est autrement la somme de termes exponentiels, est due à la présence de signes négatifs alternatifs (dont le manque rend le calcul permanent est...
La plus petite formule connue pour le déterminant a la taille selon le folklore (ou selon Ran Raz dans son papier Les formules multi-linéaires pour permanent et déterminant sont de taille super-polynomiale ).nO (logn )nO(Journaln)n^{\mathcal O(\log n)} Avez-vous une référence pour cela? En...
En comptant les arguments, on peut montrer qu'il existe des polynômes de degré n dans 1 variable (c'est-à-dire quelque chose de la forme qui ont complexité du circuit n. De plus, on peut montrer qu'un polynôme comme nécessite au moins multiplications (vous en avez besoin juste pour obtenir un degré...
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é...
Dans le célèbre contre-exemple de l'isomorphisme des graphes via la méthode de Weisfeiler-Lehman (WL), le gadget suivant a été construit dans cet article par Cai, Furer et Immerman. Ils construisent un graphe donné parXk= ( Vk, Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk= Ak∪ Bk∪ Mk où UNEk= { aje∣ 1 ≤ i ≤ k...
J'essaie de comprendre la relation entre la complexité algorithmique et la complexité du circuit des déterminants et de la multiplication matricielle. On sait que le déterminant d'unmatrice n × n peut êtrecalculéen temps ˜ O ( M ( n ) ) , où M ( n ) est le temps minimum requis pour multiplier...
Soit kkk un champ. Comme d'habitude, pour un f∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in k[x_{1},x_{2},\ldots,x_{n}] nous définissons L(f)L(f)L(f) comme la complexité linéaire de fff sur kkk . Soit FFF l'ensemble des monômes de fff , à savoir les monômes qui apparaissent en fff avec un coefficient non nul....
La matrice de Moore est similaire à la matrice de Vandermonde mais a une définition légèrement modifiée. http://en.wikipedia.org/wiki/Moore_matrix Quelle est la complexité du calcul du déterminant d'une matrice de Moore de rang complet modulo un entier?n×nn×nn \times n Le déterminant de Moore...