En lisant le blog de Dick Lipton, je suis tombé sur le fait suivant vers la fin de son billet Bourne Factor : Si, pour tout , il existe une relation de la forme où , et chacun des , et ont une longueur de bits , puis l'affacturage a un polynôme circuits de
Prenez un graphe orienté où les bords sont décorés d'un nombre naturel. On veut l'ensemble de tous les chemins entre deux sommets et telle sorte que chaque bord successif du chemin soit décoré d'un nombre naturel supérieur au nombre naturel décorant le bord précédent.ggGPPPv1v1v_1v2v2v_2 Une...
Il est connu que l'intersection de trois matroïdes généraux est NP-difficile ( source ), ce qui se fait par réduction du cycle hamiltonien. La réduction utilise un matroïde graphique et deux matroïdes de connectivité. Un cas particulier d'un problème sur lequel je travaille peut être résolu par...
Que dois-je lire pour comprendre ce problème? La puissance des circuits quantiques de faible profondeur. Est-ce que ? En d'autres termes, la partie "quantique" de tout algorithme quantique peut-elle être compressée à la profondeur du polylogue (n), à condition que nous soyons prêts à effectuer un...
Le manuscrit suivant est-il accessible au public? Dana Scott, 1969, Une théorie des fonctions calculables de type supérieur . Notes de séminaire non publiées, 7 pages, Université d'Oxford. Il y a une discussion de cet article dans la section 8.1.2, Types as sets , dans Cardone & Hindley, 2006...
Je souhaite trier un tableau de valeurs entières positives L=v1,…,vnL=v1,…,vnL = v_1, \ldots, v_n en temps linéaire (dans le modèle RAM avec mesure de coût uniforme, c'est-à-dire que les entiers peuvent avoir jusqu'à la taille logarithmique mais les opérations arithmétiques sur eux sont supposées...
Un graphique mixte est un graphique qui peut avoir à la fois des bords orientés et non orientés. Son graphe non orienté sous-jacent est obtenu en oubliant les orientations des arêtes dirigées, et dans l'autre sens, une orientation d'un graphe mixte est obtenue en affectant une direction à chaque...
De nombreuses publications informatiques des années 1950 et 1960 contiennent des spéculations philosophiques fascinantes sur la nature de l'esprit et la signification de l'information par rapport au monde physique. Des exemples célèbres sont le "Test de Turing", le "Calcul de l'espace" de Zuse, le...
Il n'y a que très peu d'informations que je peux trouver sur le problème NP-complet de la résolution de l'équation diophantienne linéaire en nombres entiers non négatifs. C'est - à - dire, est - il une solution non négatif à l'équation a 1 x 1 + a 2 x 2 + . . . + a n x n = b , où toutes les...
Un couvercle de bord est un sous-ensemble de bords d'un graphique de sorte que chaque sommet du graphique est adjacent à au moins un bord du couvercle. Les deux articles suivants indiquent que le comptage des couvertures de bord est # P-complet: Un FPTAS simple pour compter les couvertures de bord...
Étant donné un graphe non dirigé à nnn sommets, quelle est la limite d'exécution la plus connue pour trouver un sous-graphe qui est un k×kk×kk\times k -biclique? Existe-t-il des algorithmes paramétrés plus rapides que l'algorithme de temps consiste à "deviner" un côté de la biclique et à voir s'il...
Existe-t-il désormais des algorithmes / preuves plus simples pour trianguler un polygone plan en temps linéaire? Quelle est une bonne ressource sur l'état de l'art de ce fameux
Je m'intéresse à la génération de nombres pseudo-aléatoires pour la cryptographie. Outre le chapitre 5 de Menezes / Oorschot / Vanstone ; Chapitre 8 de Stinson ; et le chapitre 3 de Goldreich , où pourrais-je trouver plus? Je m'intéresse aux principes généraux de conception des PRNG (propriétés...
En lisant l'article " Une théorie applicative pour la FPH ", vous pouvez rencontrer le passage suivant: Compte tenu des théories qui caractérisent les classes de complexité informatique, il existe trois approches différentes: dans l'un, les fonctions qui peuvent être définies dans la théorie sont...
Comme tout le monde le sait, le célèbre livre de Garey et Johnson (et bien d'autres) fournit une excellente référence pour la technique de réduction en milieu classique. Existe-t-il des enquêtes ou des livres sur le thème de la technique de réduction dans l'algorithme paramétré, disons la réduction...
J'ai en fait deux questions: Qui a d'abord utilisé les relations logiques pour relier la sémantique? Je les ai retracés à " Sur la relation entre la sémantique directe et la continuation " de Reynold " , mais je ne peux pas prétendre avoir fait une recherche exhaustive. J'ai trouvé des références à...
J'utilise le terme de titre dans un sens très vague. Il y a une quantité importante de travail sur la théorie des jeux évolutifs, y compris ses fondements mathématiques. On m'a recommandé "Jeux évolutionnaires et dynamique des populations", mais je n'y suis pas encore allé. Il y a également une...
Ceci est écrit dans l'entrée wiki de Symbolic Execution , mais je ne trouve aucune référence pour cela. Quelqu'un peut-il me montrer un pointeur? Je vous
Une catégorie a des sous - produits lorsque les mêmes objets sont à la fois les produits et coproduits. Quelqu'un a-t-il étudié la théorie de la preuve des catégories avec des biproduits? L'exemple le plus connu est peut-être la catégorie des espaces vectoriels, dans laquelle la somme directe et...
Edit: Comme je n'ai reçu aucune réponse / commentaire en une semaine, je voudrais ajouter que je suis heureux d'entendre quoi que ce soit sur le problème. Je ne travaille pas dans la région, donc même si c'est une simple observation, je ne le sais peut-être pas. Même un commentaire comme "je...