Existe-t-il une notion de calculabilité sur des ensembles autres que les nombres naturels? Par souci d'argument, disons sur les ensembles qui se bijectent avec .NSSSNN\mathbb{N} Il est tentant de dire "oui, ce sont ces fonctions de la forme où est toute bijection et est toute fonction calculable "....
Le théorème de Mahaney nous dit que s'il y a un ensemble incomplet de clairsemé sous des réductions de plusieurs un en temps polynomial, alors . (Voir " Ensembles complets clairsemés pour NP: solution d'une conjecture de Berman et Hartmanis ")NPNPNPP= NPP=NPP = NP Existe-t-il des conséquences...
Je suis tombé sur deux exemples de dureté hypothétique de certains problèmes graphiques. La dureté hypothétique signifie que réfuter une conjecture impliquerait l'exhaustivité NP du problème de graphe respectif. Par exemple, la conjecture de Barnette déclare que chaque graphe bipartite planaire...
Que soit une machine déterministe polynomial qui peut poser des questions à un oracle A . Initialement, A est vide mais cela peut être modifié après un jeu qui sera décrit ci-dessous. Soit x une chaîne.MMMUNEUNEAUNEUNEAXXx Considérez le jeu Alice et Bob suivant. Initialement, Alice et Bob ont...
Que pensez-vous de lire régulièrement des articles en dehors de son domaine, même ceux qui ne sont pas liés à son domaine? Mon intuition est que cela peut donner une perspective ou une technique totalement différente qui peut m'aider dans mes propres problèmes. Mais en même temps, je suis un peu...
Existe-t-il un algorithme de tri basé sur la comparaison qui utilise une moyenne de lg(n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) comparaisons? L'existence d'un algorithme de comparaison pire des cas lg(n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n)est un problème ouvert, mais le cas moyen suffit pour un...
Existe-t-il des exemples de cas où la simulation classique d'un algorithme quantique pour un problème surpasse le meilleur algorithme classique précédemment connu pour ce problème? "Surperformances" ne signifie pas nécessairement une classe de complexité différente, il pourrait simplement s'agir...
Je suis dans une situation où je dois montrer que la vérification de typage est décidable pour un calcul typé de manière dépendante sur lequel je travaille. Jusqu'à présent, j'ai pu prouver que le système est en train de normaliser fortement, et donc que l'égalité définitionnelle est décidable....
Je suis actuellement à la recherche d'un sujet de thèse et ai rencontré le domaine de la théorie algorithmique de l'information. Le terrain me semble très intéressant, mais il semble que tout soit fait le terrain a été fait avant plusieurs années. Ma question est donc la suivante: le champ est-il...
La classe est les fonctions de classe calculables par des familles de circuits de fan-in borné, de taille et de profondeur . La est l'union de ces classes.NCjeNCi\textrm{NC}^inO ( 1 )nO(1)n^{O(1)}O ( logje( n ) )O(Journalje(n))O(\log^i(n))NCNC\textrm{NC} Existe-t-il une étude de la variante de...
Ceci est une généralisation de ma question précédente . Que soit une machine déterministe polynomial qui peut poser des questions à un oracle . Initialement, est vide mais cela peut être modifié après un jeu qui sera décrit ci-dessous. Soit une chaîne.MMMUNEUNEAUNEUNEAXXx Considérez le jeu Alice et...
On sait depuis le début des années 70 que NPNP{\bf NP} et E=DTIME(2O(n))E=DTIME(2O(n)){\bf E}=DTIME(2^{O(n)}) ne sont pas égaux (carEE{\bf E} n'est pas fermé par des réductions de plusieurs un en temps polynomial, en revanche à NPNP{\bf NP} ). Pour autant que je sache, cependant, il est toujours...
Dans le Complexity Zoo, il est dit [ 1 ] que, dans la complexité descriptive, PPP peut être défini par trois types de formules différents, FO(LFP)FO(LFP)FO(LFP) qui est aussi FO(nO(1))FO(nO(1))FO(n^{O(1)}) , et aussi comme SO(HORN)SO(HORN)SO(HORN) . Cependant, il y a quelques exceptions, par...
Je me demande si quelqu'un peut me donner l'intuition derrière pourquoi la positivité stricte des types de données inductifs garantit une forte normalisation. Pour être clair, je vois comment avoir des occurrences négatives conduit à la divergence, c'est-à-dire en définissant: data X where Intro :...
Je m'intéresse à divers sujets comme la logique combinatoire, le calcul lambda, la programmation fonctionnelle depuis un certain temps et je les étudie. Cependant, contrairement à la «Théorie du calcul» qui s'efforce de répondre à la question de la «calculabilité», c'est-à-dire des choses qui...
Nous savons que sous ETHETHETH nous ne pouvons pas résoudre KKK -SUM en temps F( K) p o l y( n K)F(K)poly(nK)f(K)poly(nK) sous n'importe quelle fonction F( K)F(K)f(K) (généralement 2O ( K)2O(K)2^{O(K)} ). Y a-t-il une conjecture qui empêche une complexité ( journaln )O ( K)(Journaln)O(K)(\log...
Le problème de correspondance parfaite bicolore consiste à décider si un graphique a une coloration à deux couleurs de sorte que chaque nœud a exactement un voisin de la même couleur que lui. Schaefer a démontré que le problème était NP-complet . Il reste NP-complet même pour les graphes cubiques...
Etant donné le graphique G1, G2 et G3, nous voulons effectuer le test d'isomorphisme F entre G1 et G2 ainsi que G1 et G3. Si G2 et G3 sont très similaires, de sorte que G3 est formé en supprimant un nœud et en insérant un nœud de G2, et nous avons le résultat de F (G1, G2), pouvons-nous calculer F...
Robin Gandy était un étudiant d' Alan Turing . Gandy a fait une analyse du moteur analytique de Babbage (voir 'Gandy - The Confluence of Ideas in 1936' cité dans 'Herken, Rolf - The Universal Turing Machine - A Half-Century Survey . Springer Verlag') - et l'a dit (cf. p. 52-53): Les fonctions...
Considérons un graphique connecté non orienté avec des poids de bord non négatifs et deux sommets distincts . Voici quelques problèmes de chemin qui sont tous de la forme suivante: trouver un chemin , de sorte qu'une fonction des poids de bord sur le chemin soit minimale. En ce sens, ils sont tous...