questions sur les limites inférieures des fonctions, généralement la complexité d'un algorithme ou un problème
L'informatique théorique a fourni quelques exemples du "prix de l'abstraction". Les deux plus importants concernent l'élimination et le tri gaussiens. À savoir: On sait que l'élimination gaussienne est optimale pour, par exemple, calculer le déterminant si vous limitez les opérations à des lignes...
Lors de la conception d'un algorithme pour un nouveau problème, si je ne trouve pas d'algorithme temporel polynomial après un certain temps, je pourrais essayer de prouver qu'il est NP-difficile à la place. Si je réussis, j'ai expliqué pourquoi je ne pouvais pas trouver l'algorithme temps...
Quelles sont les meilleures limites inférieures actuelles pour le temps et la profondeur de circuit pour
Dans les années 1980, Razborov a montré qu'il existait des fonctions booléennes monotones explicites (telles que la fonction CLIQUE) nécessitant de manière exponentielle de nombreuses portes ET et OU pour le calcul. Cependant, la base {AND, OR} sur le domaine booléen {0,1} n'est qu'un exemple d'un...
Laissez PRIMES (aka test de primalité ) être le problème: Étant donné un nombre naturel , est-il un nombre premier?nnnnnnn Soit FACTORING le problème: Soit les nombres naturels , avec , a-t-il un facteur avec ?nnnmmm1≤m≤n1≤m≤n1 \leq m \leq nnnnddd1<d<m1<d<m1 < d < m Sait-on si PRIMES...
La cupidité, faute d'un meilleur mot, est bonne. L' approche gloutonne est l'un des premiers paradigmes algorithmiques enseignés dans le cours d'introduction aux algorithmes . Une approche gloutonne donne des algorithmes simples et intuitifs pour de nombreux problèmes de P. Plus intéressant, pour...
Il y a quelques années, Joel Friedman avait écrit un article reliant les limites inférieures du circuit à la cohomologie de Grothendieck (voir articles: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Cette ligne de pensée a-t-elle apporté de nouvelles informations sur la...
Soit une fonction booléenne et considérons f comme une fonction de à . Dans ce langage, l'expansion de Fourier de f est simplement l'expansion de f en termes de monômes libres carrés. (Ces monômes forment une base pour l'espace des fonctions réelles sur . La somme des carrés des coefficients est...
Le récent résultat de la borne inférieure de la complexité du circuit de Ryan Williams fournit une technique de preuve qui utilise le résultat de la borne supérieure pour prouver la complexité des bornes inférieures. Suresh Venkat dans sa réponse à cette question, Y a-t-il des résultats...
Question: Quelle est la limite inférieure de taille de formule la plus connue pour une fonction explicite dans AC 0 ? Existe-t-il une fonction explicite avec une borne inférieure Ω(n2)Ω(n2)\Omega(n^2) ? Contexte: Comme la plupart des limites inférieures, les limites inférieures de la taille de la...
J'ai besoin de calculer la médiane en cours d'exécution: Entrée: , , vecteur .k ( x 1 , x 2 , … , x n )nnnkkk(x1,x2,…,xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Sortie: vecteur , où est la médiane de .y i ( x i , x i + 1 , … , x i + k - 1 )(y1,y2,…,yn−k+1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc,...
Il est clair que tout problème décidable dans un espace de log déterministe ( LLL ) s'exécute au maximum dans le temps polynomial ( PPP ). Il y a une multitude de classes de complexité entre LLL et PPP . Les exemples incluent NLNLNL , LogCFLLogCFLLogCFL , NCiNCiNC^i , SACiSACiSAC^i , ACiACiAC^i ,...
Je sais que trivialement la fonction OR sur nnn variables X1, … , Xnx1,…,xnx_1,\ldots, x_n peut être représentée exactement par le polynôme p ( x1, … , Xn)p(x1,…,xn)p(x_1,\ldots,x_n) comme tel: p ( x1, … , Xn) = 1 - ∏ni = 1( 1 - xje)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) = 1-\prod_{i =...
Un polynôme est une projection monotone d'un polynôme g ( y 1 , … , y m ) si m = poly ( n ) , et il y a une affectation π : { y 1 , … , y m } → { x 1 , … , x n , 0 ,f(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n)g(y1,…,ym)g(y1,…,ym)g(y_1,\ldots,y_m)mmm(n)(n)(n) tel que f ( x 1 , … , x n ) = g ( π ( y 1 ) , …...
Suite à une question précédente , quelles sont les meilleures limites inférieures de l' espace actuel pour SAT? Avec une borne inférieure d'espace, je veux dire ici le nombre de cellules de bande de travail utilisées par une machine Turing qui utilise un alphabet binaire de bande de travail. Un...
À 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...
Outre la complexité de communication (déterministe) d'une relation , une autre mesure de base pour la quantité de communication nécessaire est le numéro de partition de protocole . La relation entre ces deux mesures est connue jusqu'à un facteur constant. La monographie de Kushilevitz et Nisan...
La formulation exacte du titre est due à Anand Kulkarni (qui a proposé la création de ce site). Cette question a été posée à titre d'exemple, mais je suis incroyablement curieux. Je connais très peu de choses sur la géométrie algébrique, et en fait, je n'ai aussi qu'une compréhension superficielle...
Préambule Les systèmes de preuve interactifs et les protocoles Arthur-Merlin ont été introduits par Goldwasser, Micali et Rackoff et Babai en 1985. Au début, on pensait que le premier était plus puissant que le second, mais Goldwasser et Sipser ont montré qu'ils avaient le même pouvoir ( en ce qui...
En utilisant l'algorithme de report prospectif, nous pouvons calculer l'addition en utilisant une profondeur de taille polynomiale 5 (ou 4?) famille de circuits C 0 . Est-il possible de réduire la profondeur? Peut-on calculer l'addition de deux nombres binaires en utilisant une famille de circuits...