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 classe des algorithmes, par exemple en ne permettant pas un circuit entièrement différent pour un problème avec n variables par rapport à un problème de n + 1 variables.
Mes questions sont: 1) Il y a une description de l'uniformité uniquement en termes de circuits, et 2) Est-il possible de proposer une forme d'uniformité encore plus forte et de donner ainsi une notion encore plus restreinte de quels algorithmes efficaces (ou restreints) dans P le sont?
Précision tardive: mon intention à la question 2 concerne une classe restreinte d'algorithmes qui a "pratiquement" la même puissance que la classe des algorithmes polynomiaux.
la source
Réponses:
Je pense que la réponse à votre première question est négative: un circuit a un nombre fixe d'entrées, et donc, OMI, nous ne pouvons parler que de "familles" de circuits, plutôt que d'un seul circuit uniforme.
Concernant votre deuxième question, vous pouvez noter qu'il existe des "familles uniformes de circuits", dont la description est générée par une machine de Turing. Autrement dit, soit une famille de circuits uniforme, et soit M une machine de Turing. Alors, pour chaque n , [ C n ] = M ( 1 n ) , où [ C n ] désigne la description de C n .{Cn} M n [Cn]=M(1n) [Cn] Cn
Il existe plusieurs classes de complexité sous P, définies par des familles de circuits uniformes. Par exemple:
est la classe des problèmes de décision décidables pardes circuits booléensuniformesavec un nombre polynomial de portes et une profondeurO( log i n).NCi O(login)
la source
Ajoutant à la réponse de Sadeq ci-dessus, en examinant les classes de circuits contenues dans P, on pourrait également vouloir examiner des notions de plus en plus restrictives d'uniformité.
La notion la plus simple et la plus connue est l'uniformité P, qui est l'exigence qu'il existe une machine de Turing (déterministe) M qui produit le circuit dans le temps poly (n) (Suresh en parle également). Les versions plus restrictives de l'uniformité tentent de limiter davantage la puissance de M. Par exemple, il existe également l'uniformité de Logspace, où M est désormais requis pour s'exécuter dans l'espace O (log (n)).Cn
La notion la plus restrictive que je connaisse est l'uniformité DLOGTIME, qui est utilisée pour les petites classes de circuits. Ici, la machine M (désormais à accès aléatoire) n'a que le temps O (log n) et ne peut donc pas écrire la description de l'ensemble du circuit. La condition imposée est que, étant donné i et n, M peut écrire le ième bit de la description du circuit dans le temps O (log n).
Pour en savoir plus, voir l'article suivant: David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41 (3): 274-306 (1990).
la source
Une façon «d'unifier» les circuits et les calculs uniformes est d'exiger une procédure à complexité limitée qui prend et délivre le circuit de conseil C n . Dans le cas de P, je pense qu'exiger un générateur de temps polynomial capable de faire ce qui précède capturera P correctement.n Cn
la source
Il me semble que le point principal ici est que nous avons besoin d'un modèle de calcul uniforme pour définir l'uniformité des circuits, si la description des circuits est donnée par des moyens qui ne sont pas uniformes, les circuits peuvent être non uniformes.
la source
1) Existe-t-il une description de l'uniformité uniquement en termes de circuits?
[Il s'agit d'une version modifiée de ma réponse à la même question que vous avez posée sur le blog de Dick Lipton. Avertissement: je ne suis pas un expert.]
Oui (je pense), d'au moins deux types différents:
a) Les circuits peuvent être générés par une machine de Turing en temps polynomial dans la taille d'entrée du problème (comme mentionné dans certaines autres réponses). (Je pense que c'est la définition standard du concept.)
Cela couvre toutes les familles de circuits que nous pourrions appeler uniformes, mais en tant que définition du concept de temps P, cela réduit simplement la définition des familles de circuits à la définition des machines de Turing, ce qui n'est peut-être pas ce que vous voulez.
b) S'il existe un automate cellulaire à 1 dimension qui fait évoluer l'entrée du problème vers la solution du problème (pour un problème de décision, la solution serait un seul bit dans une cellule spécifiée par rapport aux cellules contenant l'entrée, qui est un état stable de l'AC), en temps polynomial en taille d'entrée, cela correspond alors à un circuit qui est périodique en 2D de manière simple (une unité de répétition par cellule par unité de temps), et dont l'état n'a d'importance que dans une région quadratiquement grande par rapport au temps de la solution.
Il s'agit d'un type très spécial de famille de circuits uniformes, mais suffisant pour résoudre tous les problèmes de P, car une machine de Turing peut être facilement codée en CA 1D. (Cela semble également correspondre à la définition d'uniformité DLOGTIME mentionnée dans une réponse précédente.)
(Ceci est similaire aux encodages des machines Turing en tant que circuits mentionnés dans les réponses de Gowers sur le blog de Lipton - en fait, l'un d'eux est probablement identique.)
Une façon d'encoder une machine Turing en tant qu'AC 1D: dans chaque cellule, nous représentons l'état de la bande à un moment donné, l'état de la tête de la machine Turing si elle était ici maintenant (dont la valeur n'a pas d'importance si elle n'est pas ici) , et un peu en disant si la tête est ici maintenant. De toute évidence, chacun de ces états au temps t ne dépend que de ses états de voisinage immédiat au temps t-1, ce qui est tout ce dont nous avons besoin pour que cela fonctionne en tant qu'AC.
la source