La complexité des circuits est l'étude des circuits liés aux ressources et des fonctions calculées par ces circuits.
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...
C'est une question sur la complexité du circuit. (Les définitions sont en bas.) Yao et Beigel-Tarui ont montré que chaque famille de circuits de taille possède une famille de circuits équivalente de taille de profondeur deux , où la porte de sortie est une fonction symétrique et le deuxième niveau...
Ryan Williams vient d’afficher sa limite inférieure sur ACC , la classe de problèmes qui ont des circuits de profondeur constante avec des ouvertures et des portes sans bornes AND, OR, NOT et MOD_m pour tous les m possibles. Qu'est-ce qui rend les portes MOD_m si spéciales? Ils permettent de...
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 ?
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...
J'ai pensé partager cette question car elle pourrait être intéressante pour d'autres utilisateurs ici. Supposons qu'une fonction qui est dans une classe uniforme (comme ) se trouve également dans une petite classe non uniforme (comme , c'est-à-dire non uniforme ), cela implique-t-il que la fonction...
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...
Dans son livre, Boolean Function Complexity, Stasys Jukna mentionne (page 564) que Kolmogorov croyait que chaque langue en P avait des circuits de taille linéaire. Aucune référence n'est mentionnée et je n'ai rien trouvé en ligne. Quelqu'un en sait-il plus
Dans la complexité de calcul, il existe une distinction importante entre les calculs monotones et généraux et un célèbre théorème de Razborov affirme que le 3-SAT et même MATCHING ne sont pas polynomiaux dans le modèle des circuits booléens monotones. Ma question est simple: existe-t-il un...
Quelle est la complexité de décider si un circuit avec bits d'entrée et bits de sortie calcule une permutation de ? en d'autres termes, si chaque chaîne de bits dans est une sortie du circuit pour une entrée? Cela ressemble à un problème qui a été étudié, mais je ne trouve aucune référence. nn{0,1...
Toutes mes excuses pour avoir posé une question qui doit sûrement figurer dans de nombreuses références standard. Je suis curieux de savoir exactement la question dans le titre, en particulier je pense aux circuits booléens, sans limite de profondeur. J'ai mis "le plus petit" entre guillemets pour...
Récemment, Ryan Willams a prouvé que la constructivité dans la preuve naturelle est inévitable pour dériver une séparation des classes de complexité: et . T C 0N E X PNEXP\mathsf{NEXP}T C0TC0\mathsf{TC}^{0} La constructivité dans la preuve naturelle est une condition que toutes les preuves...
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...
EDIT (v2): Ajout d'une section à la fin sur ce que je sais du problème. EDIT (v3): Ajout d'une discussion sur le degré de seuil à la fin. Question Cette question est principalement une demande de référence. Je ne connais pas grand-chose au problème. Je veux savoir s'il y a eu des travaux antérieurs...
Dans l'enquête "Small Depth Quantum Circuits" de D. Bera, F. Green et S. Homer (p. 36 de ACM SIGACT News, juin 2007 vol. 38, no. 2) , j'ai lu la phrase suivante: La version classique de (dans laquelle les portes et ont un fanout au plus constant) est manifestement plus faible que . A N D O R A C 0Q...
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 ) , …...
L'état de nos connaissances sur les circuits arithmétiques généraux semble être similaire à l'état de nos connaissances sur les circuits booléens, c'est-à-dire que nous n'avons pas de bonnes limites inférieures. D'un autre côté, nous avons des limites inférieures de taille exponentielle pour les...
À 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...
Existe-t-il une hypothèse plausible de complexité / cryptographie qui exclut la possibilité que les circuits de taille polynomiale aient des circuits de taille sous-exponentielle (c'est-à-dire avec ϵ < 1 ) à profondeur limitée ( d = O ( 1 )
capture l'idée d'une parallélisation efficace, et une interprétation de celui-ci est les problèmes qui peuvent être résolus dans le temps O ( log c n ) en utilisantdes processeurs parallèles O ( n k ) pour certaines constantes c , k . Ma question est de savoir s'il existe une classe de complexité...