Ma question est pourquoi les bornes inférieures pour les circuits booléens de profondeur 3 avec les portes "et" et "xor" pour le déterminant n'impliquent pas les mêmes bornes inférieures pour les circuits arithmétiques sur ?ZZ\mathbb{Z} Quel est le problème avec l'argument suivant: Soit un...
Soit un polynôme donné par un circuit arithmétique C de taille s . Étant donné C comme entrée, existe-t-il un algorithme déterministe pour vérifier si tous les facteurs irréductibles de f dans Q [ x 1 , x 2 , … , x n ] sont des formes linéaires? Sur une note connexe, étant donné une forme linéaire...
Soit un polynôme à n variables donné comme un circuit arithmétique de taille poly ( n ) , et soit p = 2 Ω ( n ) un nombre premier.fffnnn(n)(n)(n)p=2Ω(n)p=2Ω(n)p = 2^{\Omega(n)} Pouvez-vous tester si est identique à zéro sur Z p , avec un temps poly ( n ) et une probabilité d'erreur ≤ 1 - 1 / poly (...
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...