Y a-t-il quelque chose dans la littérature proche du problème suivant: Étant donné un graphe biparti avec bipartition équilibrée { U , W } , existe-t-il une correspondance parfaite M dans G telle que pour chaque 2 arêtes u 1 w 1 , u 2 w 2 ∈ M , il y a une arête u 1 w 2 ou bord u 2 w 1 (ou les deux)...
Le "nom du jeu le plus grand nombre" demande à deux joueurs d'écrire un numéro secrètement, et le gagnant est la personne qui a écrit le plus grand nombre. Le jeu permet généralement aux joueurs d'écrire des fonctions évaluées à un moment donné, donc serait également une chose acceptable à...
Le problème de la représentation des variables liées dans la syntaxe, et en particulier celui de la substitution évitant la capture, est bien connu et a plusieurs solutions: variables nommées avec équivalence alpha, indices de Bruijn, localement sans nom, ensembles nominaux, etc. Mais il semble y...
Dans la théorie de la complexité, la définition de la complexité du temps et de l'espace fait référence à une machine de Turing universelle: resp. le nombre d'étapes avant de s'arrêter et le nombre de cellules sur la bande touchées. Compte tenu de la thèse de Church-Turing, il devrait également...
D'après le théorème de la hiérarchie spatiale, on sait que si fff est constructible dans l'espace, alors DSPACE ( 2f(n)2f(n)2f(n) ) n'est pas égal à DSPACE ( f(n))f(n))f(n)) . Ici, par DSPACE ( f(n))f(n))f(n)) je veux dire la classe de tous les problèmes qui peuvent être résolus dans l'espace...
J'ai lu des informations sur la substitution héréditaire pour le calcul lambda simple et pour le cadre logique avec des termes et des types distincts. Je me demande, existe-t-il des exemples de substitution héréditaire dans un système typé de façon dépendante avec une hiérarchie d'univers?...
Un ensemble de mots sur un alphabet fini est sans préfixe s'il n'y a pas deux mots distincts où l'un est un préfixe de l'autre. La question est: Quelle est la complexité de vérifier si un langage régulier donné en NFA contient un sous-ensemble infini sans préfixe? Réponse (grâce à Mikhail Rudoy,...
Les progrès de l'informatique quantique ont conduit au développement de nouveaux algorithmes classiques. Des exemples récents notables sont des algorithmes d'inspiration quantique pour l'algèbre linéaire: Un algorithme classique d'inspiration quantique pour les systèmes de recommandation...
On dit que deux groupes et sont isomorphes s'il existe un homomorphisme de en qui est bijectif. Le problème d'isomorphisme de groupe est le suivant: étant donné deux groupes, vérifiez s'ils sont isomorphes ou non. Il existe différentes façons de saisir un groupe, les deux plus utilisées sont par...
Dans l'article de Stephen Cook sur le problème P vs NP [1], il déclare ce qui suit [2]: Thèse de faisabilité: Un problème naturel a un algorithme réalisable s'il a un algorithme polynomial. Ma question est, que veut-il dire exactement (ou en général, qu'est-ce que l'on entend) par "un problème...
La nature diviser pour mieux régner de la FFT peut-elle être généralisée à d'autres transformations (Transformation z, gazouillis, etc.) automatiquement? Existe-t-il un algorithme qui prend une description de la transformation (je ne sais pas quelles informations seraient nécessaires) et peut...
Plus précisément, je demande des ressources pour en savoir plus sur les systèmes d'apprentissage automatique qui peuvent mettre à jour leurs réseaux de croyances respectifs (ou équivalent) pendant le fonctionnement. J'en ai même rencontré quelques-uns, même si je n'ai pas réussi à les mettre en...
Le théorème de zone dit que si nous poignardons un arrangement de n lignes avec une autre ligne, la complexité totale de sa zone , l'ensemble de toutes les faces 0, 1 et 2 adjacentes, est O (n). La constante réelle est quelque chose comme 6n au moins comme indiqué dans divers manuels, et la preuve...
Il existe plusieurs notions différentes (probablement inéquivalentes) d'universalité informatique (voir par exemple les deux dernières pages de http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) et il n'y a pas de consensus entre des experts sur les notions les plus correctes...
Soit un graphe connecté non régulier dont le degré est borné. Supposons que chaque nœud contienne un jeton unique.G=(V,E)G=(V,E)G= (V, E) Je veux mélanger uniformément les jetons parmi le graphique en utilisant uniquement des swaps locaux (c'est-à-dire l'échange des jetons entre deux nœuds...
La plupart de la littérature semble s'intéresser aux machines à oracles simples pour des problèmes spécifiques, mais il semble y avoir quelques articles qui considèrent les machines à oracles multiples. Existe-t-il un bon article ou une thèse qui donne un aperçu de ce que l'on sait de ces machines?...
Quelles sont les preuves que ?coRP≠NPcoRP≠NPcoRP \neq NP coRPcoRPcoRP est la classe de langues pour laquelle il existe une machine de Turing probabiliste qui fonctionne en temps polynomial et répond toujours Oui sur une entrée appartenant à la langue et répond Non avec une probabilité d'au moins la...
Est-il possible (barre oblique pouvez-vous fournir un exemple) de réduire la complexité de calcul d'un problème en utilisant un algorithme parallèle qui ne nécessite pas un certain nombre de processeurs par rapport à la taille
Par BPP / linéaire, je me réfère aux machines BPP avec conseil linéaire, qui remplissent la promesse quand on leur donne le conseil "correct", et la dérandomisation devrait nous donner, disons, un algorithme P / linéaire ou (SUBEXP / linéaire). Si nous utilisons des hypothèses non uniformes, je...
Dans SODA 1995 , Jeff Erickson a montré des limites inférieures pour la satisfiabilité linéaire (vérifier si un certain ensemble de n nombres réels satisfait une équation linéaire sur r variables). La méthode de preuve utilise des infinitésimales et le principe de transfert de Tarski .rrrnnnrrr...