Un modèle de calcul dans lequel le calcul est décrit via des circuits de différentes portes logiques.
Je sais que les opérations binaires sont très rapides sur les processeurs modernes, car ils peuvent fonctionner en parallèle sur 32 ou 64 bits. Les opérations binaires ne prennent donc qu'un cycle d'horloge. Toutefois, l’ajout est une opération complexe qui consiste en au moins une, voire une...
Concernant la porte quantique de Toffoli : est-ce universellement classique , et si oui, pourquoi? est-ce quantiquement universel, et pourquoi?
Après la sortie de la bibliothèque AIGER pour gérer les graphiques et les onduleurs en 2006 (je pense), certains solveurs SAT de circuits ont été publiés en 2006-2008, et dans quelques courses / compétitions SAT, il y avait des pistes AIG. Cependant, depuis lors, il semble que l'accent ait été...
Je sais que les portes NAND peuvent être utilisées pour créer des circuits qui implémentent chaque table de vérité, et les ordinateurs modernes sont constitués de portes NAND. Quel est le lien théorique entre les portes NAND et l'exhaustivité de Turing? Il me semble que les circuits de porte NAND...
Par exemple, je sais que la langue non régulière est en . J'aimerais en savoir plus d'exemples comme
Je ne peux pas comprendre comment fonctionne le verrou SR. Apparemment, vous branchez une ligne d'entrée de R, et une autre de S, et vous êtes censé obtenir des résultats dans et Q ' .QQQQ′Q′Q' Cependant, les deux R et S nécessitent une entrée de la sortie de l'autre, et la sortie de l'autre...
La définition de P est un langage qui peut être décidé par un algorithme de temps polynomial. La définition de P / poly peut être interprétée comme signifiant un langage qui peut être décidé par un circuit de taille polynomiale (voir http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf )....
Il est bien connu que chaque fonction booléenne peut être réalisée en utilisant un circuit booléen de profondeur 2 (sur les variables, leur négation et leurs valeurs constantes) contenant des portes ET au premier niveau et une seule porte OU au niveau supérieur; c'est simplement la représentation...
Dis que tu as mmm entrées booléennes, et vous êtes donné un seuil nnn. Vous devez construire un circuit booléen qui est évalué à vrai si au moinsnnndes entrées vrai. Vous pouvez utiliser les portes ET, OU, NON ou XOR (limité au fan-in two, avec arbitraire fan-out). Asymptotiquement, comment...
D'après ce que j'ai compris: Une bascule est un verrou cadencé, c'est-à-dire une bascule = verrou + horloge Le verrou vérifie en permanence les entrées et modifie la sortie chaque fois qu'il y a un changement d'entrée Flip Flop vérifie également en continu l'entrée, mais modifie le temps de sortie...
J'essaie de relier les circuits logiques multinationaux (ordinateurs basés uniquement sur des portes logiques) avec tout ce que j'ai appris récemment dans la théorie du calcul. Je me demandais si les circuits logiques combinatoires peuvent implémenter des calculs de la même manière que les machines...
L'exercice 4.29 du calcul quantique et des informations quantiques de Nielsen et Chuang m'a déconcerté. Trouver un circuit contenant Toffoli, CNOT et des portes à qubit unique qui implémente une porte (pour ), en utilisant aucun qubits de travail.O (n2)O(n2)O(n^2)Cn( X)Cn(X)C^n(X)n > 3n>3n >...
Tests d'identité polynomiale est l'exemple type d'un problème connu pour être co-RP mais pas connu pour être en P . Sur les circuits arithmétiques , cela semble en effet difficile, car le degré du polynôme peut être rendu exponentiellement grand par quadrature répétée. Cette question aborde la...