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...
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 /...
J'ai remarqué que les langues régulières sur l'alphabet peuvent naturellement être considérées comme un poset, et même un treillis. De plus, la concaténation avec le langage vide définit une structure monoïdale stricte sur cette catégorie qui est distributive sur les jointures (je ne suis pas sûr...
Y a-t-il un exemple d'un problème naturel qui est dans BPP mais qui n'est pas connu pour être RP ou
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...
Je suis un étudiant de premier cycle et j'ai récemment accepté le fait que je n'ai peut-être pas l'intellect pour faire des recherches en informatique théorique, ou être en mesure d'être admis et de terminer un programme de doctorat. Cependant, je voudrais quand même m'impliquer dans l'informatique...
O(nlogn)O(nlogn)O(n\log n)1+O(n−c)1+O(n−c)1+O(n^{-c})cccO(n)O(n)O(n)(max−min)n−(c+1)(max−min)n−(c+1)(\max-\min)n^{-(c+1)}de sa valeur d'origine, puis utilisez le tri radix. Mais les modèles avec arrondi ont une théorie de complexité problématique et cela m'a amené à me demander, qu'en est-il des...
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
J'enseignerai un cours de premier cycle standard sur les langues et les automates au semestre prochain, et je préférerais utiliser un texte légitime gratuit ou à faible coût. Aucune suggestion? J'adore le texte Sipser mais la dernière édition coûte 196 $, ce qui est difficile à dire avec un visage...
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...
Selon l'article de KW Regan "Connect the Stars" , il mentionne à la fin qu'il est toujours difficile de trouver une représentation des nombres entiers de sorte que les opérations d'addition, de multiplication et de comparaison sont calculables en temps linéaire: Existe-t-il une représentation...
Nous savons tous que la distinction des éléments dans le modèle basé sur la comparaison ne peut pas être effectuée en temps . Cependant, sur un mot-RAM, on peut éventuellement obtenir de meilleurs résultats.o(nlogn)o(nJournaln)o(n\log n) Bien sûr, si l'on suppose l'existence d'une fonction de...
En raisonnant un peu sur cette question , j'ai essayé d'identifier toutes les différentes raisons pour lesquelles un graphe peut ne pas être k colorable. Ce sont les 2 seules raisons que j'ai pu identifier jusqu'à présent:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk contient une clique de taille k + 1 ....
Il existe de nombreux endroits où les nombres ππ\pi et ( 1 + 5-√) / 2(1+5)/2(1+\sqrt5)/2apparaissent. Je suis curieux de connaître les algorithmes dont le temps d'exécution contient le nombre d'or ouππ\pidans
Contexte: Soit u,vu,vu, v deux sommets d'un graphe non orienté . Un ensemble de sommets est un séparateur si et appartiennent à différents composants connectés de . Si aucun sous-ensemble correct d'un séparateur est un séparateur, alors est un séparateur minimal. Un ensemble de sommets est un...
Dans une catégorie cartésienne ( CCC ), il existe les soi-disant objets exponentielles , écrit . Lorsqu'un CCC est considéré comme un modèle de simplement typé -calcul , un objet exponentielle comme caractérise l'espace de fonction à partir du type type . Un objet exponentiel est introduit par une...
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...
Existe-t-il un moyen (raisonnable) d'échantillonner une fonction booléenne uniformément aléatoire dont le degré en tant que polynôme réel est au plus ?dF: { 0 , 1 }n→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}rédd EDIT: Nisan et Szegedy ont montré qu'une fonction du degré dépend au plus de...
Considérez la langue .EQUALITY={anbn∣n≥0}EQUALITY={anbn∣n≥0} \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} Il est connu que ne peut être reconnu par aucune machine de Turing à espace sublogarithmique alternatif (ATM) (Szepietowski, 1994) . (Il existe un guichet automatique utilisant un espace...