Nous connaissons beaucoup les limites des circuits (taille polynomiale) à profondeur constante. Étant donné que les formules à profondeur constante (taille polynomiale) sont un modèle de calcul encore plus restreint, tous les problèmes connus pour ne pas être en AC 0 ne sont pas non plus...
La meilleure borne supérieure connue sur la complexité temporelle de la multiplication est la borne Martin Fürer , qui est plus qu'une complexité temporelle linéaire de l'addition. Avons-nous la preuve que l'addition est intrinsèquement plus facile que la
La porte ET & OU est une porte qui reçoit deux entrées et renvoie leur ET et leur OU. Les circuits fabriqués uniquement à partir de la porte AND & OR, sans fanout, sont-ils capables de faire des calculs arbitraires? Plus précisément, l'espace de journalisation du calcul du temps polynomial...
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 )
Lorsque limité à 000 - 111 entrées, chaque {+,×}{+,×}\{+,\times\} -Circuit F(x1,…,xn)F(x1,…,xn)F(x_1,\ldots,x_n) calcule une fonction F:{0,1}n→NF:{0,1}n→NF:\{0,1\}^n\to \mathbb{N} . Pour obtenir une fonction booléenne , nous pouvons simplement ajouter une porte seuil fanin-1 comme porte de sortie....
De nombreux résultats importants dans la théorie de la complexité computationnelle, et en particulier la théorie de la complexité "structurelle", ont la propriété intéressante de pouvoir être compris comme suivant fondamentalement (comme je le vois ...) des résultats algorithmiques donnant un...
Considérez le raisonnement suivant: Soit la complexité de Kolmogorov de la chaîne . Le théorème d'incomplétude de Chaitin dit quexK( x )K(x)K(x)Xxx pour tout cohérent et système formel suffisamment solide , il existe une constante (ne dépendant que du système formel et sa langue) de telle sorte que...
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...
C'est un résultat classique que chaque circuit fan-in 2 ET-OU-NON qui calcule la PARITÉ à partir des variables d'entrée a une taille d'au moins , ce qui est net. (Nous définissons la taille comme le nombre de portes ET et OU.) La preuve est par élimination de porte et elle semble échouer si nous...
(Von Neumann a donné un algorithme qui simule une pièce équitable donnant accès à des pièces biaisées identiques. L'algorithme nécessite potentiellement un nombre infini de pièces (bien qu'en attente, un nombre fini suffira). Cette question concerne le cas où le nombre de lancers autorisés est...
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...
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é...
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Définissons maintenant les ensembles de toutes les entrées avec la complexité de Kolmogorov , et définissons la séquence Ici est la séquence de...
Comme nous le savons, la fonction kkk -clique CLIQUE(n,k)CLIQUE(n,k)CLIQUE(n,k) prend un sous-graphe ( couvrant ) d'un graphe sommet complet , et les sorties si contient une -clique . Les variables dans ce cas correspondent aux arêtes de K n . On sait (Razborov, Alon-Boppana) que, pour 3 ≤ k ≤ n /...
En complexité paramétrée, ⊆ W [ 2 ] ⊆ … ⊆ W [ P ] . On suppose que chacune des enceintes est appropriée.F P T ⊆ W [1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆W[2]⊆W[2]\subseteq \mathsf{W}[2] ⊆…⊆W[P]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Si alors P = W [ P ]...
Dans le document "A Compendium of Problems Complete for P" de Greenlaw, Hoover et Ruzzo (PS) (PDF) , il y a une liste de problèmes dans P qui ne sont pas connus pour être en NC et pas connus pour être P-complete non plus. . (Cette liste résume tous les problèmes ouverts dans l'excellente enquête de...
Discussion : J'ai passé un peu de temps récemment à apprendre différentes choses sur la complexité de la communication. Par exemple, je me suis familiarisé avec le chapitre pertinent d'Arora / Barak, j'ai commencé à lire certains articles et commandé le livre de Kushilevitz / Nisan. Intuitivement,...
Le théorème de Karp – Lipton déclare que si , alors s'effondre en . Par conséquent, en supposant des séparations entre et , aucun problème complet n'appartiendra à .P H Σ P 2 Σ P 2 Σ P 3 N P P / p o l yN P ⊂ P / p o l yNP⊂P/poly\mathsf{NP} \subset \mathsf{P/poly}P
Deux questions connexes sur l'informatique en profondeur limitée: 1) Supposons que vous commenciez par n bits et que vous commenciez par le bit i peut être 0 ou 1 avec une certaine probabilité p (i), indépendamment. (Si cela rend le problème plus simple, nous pouvons supposer que tous les p (i) s...
Supposons que nous ayons un problème paramétré par un paramètre de valeur réelle p qui soit "facile" à résoudre lorsque et "difficile" lorsque p = p 1 pour certaines valeurs p 0 , p 1 .p = p0p=p0p=p_0p = p1p=p1p=p_1p0p0p_0p1p1p_1 Un exemple est le comptage des configurations de spin sur les...