Questions marquées «circuit-complexity»

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...

EDIT (22 août 2011): Je simplifie encore la question et je mets à contribution la question. Peut-être que cette question plus simple aura une réponse facile. Je vais également biffer toutes les parties de la question initiale qui ne sont plus pertinentes. (Merci à Stasys Jukna et Ryan O'Donnell...

La borne inférieure Blum est la borne inférieure du circuit la plus connue sur la base complète d'une fonction explicite , cf. Réponse de Jukna à cette question pour des résultats connexes.f : { 0 , 1 } n → { 0 , 1 }3 n - o ( n )3n-o(n)3n-o(n)F: { 0 , 1 }n→ { 0 , 1 }F:{0,1}n→{0,1}f : \{0,1\}^n \to...

Une partie des travaux sur la sensibilité par rapport à la sensibilité aux blocs visait à examiner les fonctions avec un écart aussi grand que possible entre s(f)s(f)s(f) et bs(f)bs(f)bs(f) afin de résoudre la conjecture selon laquelle bs(f)bs(f)bs(f) n'est que polynomialement plus grand que...

Un circuit booléen non déterministe possède, en plus des entrées ordinaires , un ensemble d'entrées "non déterministes" . Un circuit non déterministe accepte l'entrée s'il existe tel que la sortie du circuit sur . Analogue à (la classe de langues décidables par des circuits de taille polynomiale),...

Comme cela est bien connu, la PARITÉ ne peut pas être effectuée dans des circuits de profondeur constante de taille poly, et en fait, les circuits const-dept nécessitent un nombre de portes EXP. Qu'en est-il des circuits QUANTUM? a) La PARITE peut-elle être effectuée avec un circuit quantique qui a...

La complexité des circuits en profondeur bornée est l'un des principaux domaines de recherche de la théorie de la complexité des circuits. Cette rubrique a des origines dans des résultats comme "la fonction de parité n'est pas dans " et "la fonction mod n'est pas calculée par ", où est la classe...

On sait que la taille minimale des U_2 calculant la fonction de parité est exactement égale à . La preuve de la borne inférieure est basée sur la méthode d'élimination des portes.U2U2U_23 ( n - 1 )3(n-1)3(n-1) Récemment, j'ai remarqué que la méthode d'élimination de porte fonctionne bien également...

Quel est le nombre minimal de portes binaires nécessaires pour calculer ET et OU de bits d'entrée simultanément? La borne supérieure triviale est . Je pense que c'est optimal, mais comment le prouver? La technique d'élimination de porte standard ne fonctionne pas ici car en attribuant une constante...

Le célèbre Picture of The World de Neil Immerman est le suivant (cliquez pour agrandir):                                         Sa classe "Vraiment faisable" ne comprend aucune autre classe; ma question est alors: Qu'est-ce qu'un problème AC 0 considéré comme peu pratique et pourquoi?...

Nous savons (pour le moment environ 40 ans, merci Adleman, Bennet et Gill) que l'inclusion BPP P / poly, et un BPP / poly P / poly encore plus fort . Le "/ poly" signifie que nous travaillons de manière non uniforme (un circuit séparé pour chaque longueur d'entrée ), tandis que P sans ce "/ poly"...

Le problème suivant apparaît dans la liste d'Aaronson Dix demi-grands défis pour la théorie de l'informatique quantique . Est-ce que BQP=BPPBQNCBQP=BPPBQNC\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} En d'autres termes, la partie "quantique" de n'importe quel algorithme quantique peut-elle être...

Une lacune que j'ai toujours su que je ne comprends pas vraiment est entre la complexité de calcul non uniforme et uniforme où la complexité du circuit représente la version non uniforme et les machines de Turing où les choses sont uniformes. Je suppose que "uniforme" est un moyen de restreindre la...

Les preuves naturelles sont une barrière pour prouver les limites inférieures de la complexité des circuits des fonctions booléennes. Ils ne signifient pas directement une telle barrière à prouver minorations sur le complexité du circuit. Y a-t-il des progrès vers l'identification de tels...

Contexte Une formule à lecture unique sur un ensemble de portes (également appelée base) est une formule dans laquelle chaque variable d'entrée apparaît une fois. Les formules à lecture unique sont communément étudiées sur la base de De Morgan (qui a les portes 2 bits ET et OU, et la porte 1 bit...

Supposons que l'on nous donne un ensemble de n variables booléennes x_1, ..., x_n et un ensemble de m fonctions y_1 ... y_m où chaque y_i est le XOR d'un sous-ensemble (donné) de ces variables. Le but est de calculer le nombre minimum d'opérations XOR que vous devez effectuer pour calculer toutes...

Je voudrais demander des suggestions de bons textes qui introduisent la complexité du circuit. Des indications sur les avancées récentes et les problèmes ouverts dans ce domaine seraient également

Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...

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...

Dans le document Natural Proofs de Razborov-Rudich , page 6, dans la partie, ils expliquent qu'il existe de "solides preuves de limites inférieures contre les modèles de circuits monotones " et comment elles s'intègrent dans l'image, il y a les phrases suivantes: Ici, le problème n'est pas la...