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 )
Existe-t-il un problème naturel dans P pour lequel la limite de temps d'exécution la plus connue est de la forme , où α est une constante irrationnelle ?O (
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...
Je suis curieux au sens large de ce que l'on sait des algorithmes de parallélisation en P. J'ai trouvé l'article wikipedia suivant sur le sujet: http://en.wikipedia.org/wiki/NC_%28complexity%29 L'article contient la phrase suivante: On ne sait pas si NC = P, mais la plupart des chercheurs...
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...
Appelons une fonction superpolynomiale si vaut pour chaque c> 0 .f(n)f(n)f(n) limn→∞nc/f(n)=0limn→∞nc/f(n)=0\lim_{n\rightarrow\infty} n^c/f(n)=0c>0c>0c>0 Il est clair que pour tout langage il contient pour chaque temps superpolynomial lié f (n) . Je me demande si l'inverse de cette...
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...
Quelle est la relation entre les algorithmes ADN et les classes de complexité définies à l'aide des machines de Turing? À quoi correspondent les mesures de complexité comme le temps et l'espace dans les algorithmes ADN? Peuvent-ils être utilisés pour résoudre des cas de problèmes NP-complets comme...
Je sais que la complexité de la plupart des variétés de calculs lambda typés sans la primitive combinateur Y est bornée, c'est-à-dire que seules les fonctions de complexité bornée peuvent être exprimées, la borne devenant plus grande à mesure que l'expressivité du système de types croît. Je...
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
Il est bien connu que le problème suivant est PSPACE-complete: Étant donné l'expression régulière , ?L ( β ) = Σ ∗ββ\betaL ( β) = Σ∗L(β)=Σ∗L(\beta) = \Sigma^* Qu'en est-il de la détermination de l'équivalence avec d'autres expressions régulières (fixes) ?αα\alpha Étant donné l'expression régulière...
Motivé par la réponse de Shor liée à différentes notions de NP-complétude, je recherche un problème qui est NP-complet sous les réductions de P mais qui n'est pas connu pour être NP-complet sous les réductions de Logspace (de préférence depuis longtemps). De plus, est-il plus difficile de trouver...
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...
Shor a déclaré, dans son commentaire à la réponse d'un orignal anonyme à cette question Pouvez-vous identifier la somme de deux permutations en temps polynomial? , qu'il est complet d'identifier la différence de deux permutations. Malheureusement, je ne vois pas de réduction directe du problème de...
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...
Récemment, j'ai vécu l' expérience douloureuse et amusante d'expliquer de manière informelle le concept de complexité informatique à un jeune programmeur autodidacte talentueux, qui n'avait jamais suivi de cours formel en algorithmes ou en complexité auparavant. Sans surprise, beaucoup de notions...
Le problème suivant est récemment apparu dans mes recherches. N'étant pas un expert des questions algorithmiques, j'ai beaucoup recherché sur Google dans la recherche de problèmes appropriés à réduire. Je ne vois pas comment 3SAT fonctionnerait, et même si ZOE est similaire dans l'esprit, une...