J'essaie de comprendre la complexité des fonctions exprimables via les portes de seuil et cela m'a conduit à . En particulier, je suis intéressé par ce que l'on sait actuellement sur l'apprentissage dans , car je ne suis pas un expert dans le domaine.T C0TC0\mathsf{TC}^0T C0TC0\mathsf{TC}^0 Ce que...
Le problème suivant apparaît dans la liste d'Aaronson Dix demi-grands défis pour la théorie de l'informatique quantique . Est-ce que BQP=BPPBQNCBQP=BPPBQNC\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} En d'autres termes, la partie "quantique" de n'importe quel algorithme quantique peut-elle être...
J'ai lu que la programmation linéaire entière est résoluble en temps polynominal si le nombre de variables est fixe, c'est-à-dire n ∈ O ( 1 ) . Si le nombre de variables croît logarithmiquement, c'est-à-dire n ∈ O ( log 2 ( N ) ) pour une entrée donnée de taille N , le problème est-il toujours...
Quels sont quelques exemples de paires de classes de complexité et B telles queAAABBB on ne sait pas si , etA=BA=BA=B nous ne connaissons pas non plus de relativisations contradictoires (c'est-à-dire que nous ne connaissons pas les oracles et Q tels que A P = B P et A Q ≠ B Q )?PPPQQQAP=BPAP=BPA^P...
Avertissement: je connais très peu la théorie de la complexité. Je suis désolé mais il n'y a vraiment aucun moyen de poser cette question sans être (terriblement) concis: Quels devraient être les morphismes dans "la" catégorie des machines de Turing? Ceci est évidemment subjectif et dépend de...
Un de mes étudiants a récemment posé la question suivante: SupposonsDoit-il exister un h (n) tel que DTIME (f (n)) \ subsetneq DTIME (h (n)) \ subsetneq DTIME (g (n))?DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n)) \subsetneq
Le théorème de Savitch montre que pour toutes les fonctions suffisamment grandes f , et prouver que cela est serré est un problème ouvert depuis des décennies .N S P A C E (f( n ) ) ⊆ D S P A C E ( f( n )2)NSPUNECE(F(n))⊆réSPUNECE(F(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)FFf...
Nous savons (pour le moment environ 40 ans, merci Adleman, Bennet et Gill) que l'inclusion BPP P / poly, et un BPP / poly P / poly encore plus fort . Le "/ poly" signifie que nous travaillons de manière non uniforme (un circuit séparé pour chaque longueur d'entrée ), tandis que P sans ce "/ poly"...
Quelle est la variation suivante sur la couverture de l'ensemble appelée? Etant donné un ensemble S, une collection C de sous-ensembles de S et un entier positif K, existe-t-il K ensembles en C tels que chaque paire d'éléments de S se trouve dans l'un des sous-ensembles sélectionnés. Remarque: Il...
Étant donné un langage L défini par une machine de Turing qui le décide, est-il possible de déterminer algorithmiquement si L se situe dans
On dit qu'un problème P est dans APX s'il existe une constante c> 0 telle qu'un algorithme d'approximation polynomiale en temps existe pour P avec le facteur d'approximation 1 + c. APX contient PTAS (vu en choisissant simplement n'importe quelle constante c> 0) et P. APX est-il dans NP? En...
Une classe héréditaire de structures (par exemple des graphiques) est une classe qui est fermée sous des sous-structures induites, ou de manière équivalente, est fermée sous suppression de vertex. Les classes de graphiques qui excluent un mineur ont de belles propriétés qui ne dépendent pas du...
Toutes mes excuses à l'avance si cette question est trop simple. Fondamentalement, ce que je veux savoir, c'est s'il existe des fonctions f(x)F(X)f(x) avec les propriétés suivantes: Prenez pour être lorsque le domaine et le domaine de codage sont limités à des chaînes à bits. alorsf ( x )...
Ceci fait suite à cette question et est lié à cette question de Shiva Kinali. Il semble que les preuves dans ces articles ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) utilisent des théorèmes de hiérarchie. Je veux savoir si les preuves sont des théorèmes de diagonalisation "...
Je suis toujours intrigué par le manque de preuves numériques des mathématiques expérimentales pour ou contre la question P vs NP. Bien que l'hypothèse de Riemann ait des preuves à l'appui de la vérification numérique, je ne connais pas de preuves similaires pour la question P vs NP. De plus, je ne...
Les preuves naturelles sont une barrière pour prouver les limites inférieures de la complexité des circuits des fonctions booléennes. Ils ne signifient pas directement une telle barrière à prouver minorations sur le complexité du circuit. Y a-t-il des progrès vers l'identification de tels...
Dans une présentation de 2006 intitulée EXPANDER GRAPHS - Y A-T-IL DES MYSTÈRES À GAUCHE? , Nati Linial a posé le problème ouvert suivant: Quel problème de calcul dur sur le graphique reste difficile lorsqu'il est limité aux graphiques d'extension?NPNPNP Depuis lors, des progrès ont-ils été...
Savitch a donné un algorithme déterministe pour résoudre la st-connectivité en utilisant l' espace , impliquant . L'algorithme de Savitch s'exécute dans le temps 2 ^ {O ({\ log} ^ 2 {n})} . C'est un problème ouvert majeur si la connectivité st peut être résolue par un algorithme déterministe dans...
Dans le document Natural Proofs de Razborov-Rudich , page 6, dans la partie, ils expliquent qu'il existe de "solides preuves de limites inférieures contre les modèles de circuits monotones " et comment elles s'intègrent dans l'image, il y a les phrases suivantes: Ici, le problème n'est pas la...
Il est difficile de trouver une approximation à facteur constant du cycle le plus long dans les graphiques hamiltoniens cubiques. Les graphiques hamiltoniens cubiques ont au moins deux cycles hamiltoniens.NPNPNP Quelles sont les limites supérieure et inférieure les plus connues sur le nombre de...