Merlin, qui a des ressources informatiques illimitées, veut convaincre Arthur que m|∑p≤N, p primepkm|∑p≤N, p primepkm|\sum_{p\le N,\ p\text{ prime}}p^k pour (N,m,k)(N,m,k)(N,m,k) avec k=O(logN)k=O(logN)k=O(\log N) et m=O(N).m=O(N).m=O(N). Le calcul simple de cette somme (exponentiation modulaire...
J'essaie de trouver des problèmes dont la complexité de l'espace moyen des cas a été analysée. Plus précisément, je suis intéressé de savoir s'il y a des problèmes avec une borne inférieure de complexité d'espace prouvée qui est super-linéaire, et surtout s'il y en a avec une analyse de cas moyen...
Nurikabe est un puzzle de remplissage de grille basé sur des contraintes, semblable à celui du Démineur / Nonogrammes; les nombres sont placés sur une grille qui doit être remplie avec des valeurs d'activation / désactivation pour chaque cellule, chaque nombre indiquant une région de cellules...
J'ai un problème qui se trouve dans NEXP et peut également être résolu par une MT alternative utilisant le temps exponentiel et une seule alternance (commençant dans un état existentiel).NPNP^{\text{NP}} Connaît-on NEXP NP ? Est-il égal à NEXP ou à une autre classe? Y a-t-il des problèmes complets...
L'exhaustivité et la solidité des systèmes de preuve interactifs sont définies de manière informelle comme: Exhaustivité: Si une déclaration est vrai, l' honnête prouveur peut convaincre l' honnête vérificateur de ce fait PVT . Solidité: si une déclaration est fausse, le prouveur de fraude ne peut...
Je ne me souviens pas d'avoir vu une séparation de classes non basée sur des résultats de diagonalisation et de relativisation. La diagonalisation pourrait toujours être utilisée pour séparer les classes connues restantes, car des arguments non relativisants pourraient toujours être utilisés dans...
En 1975, Miller a montré comment réduire la factorisation de l'entier pour trouver la période d'une fonction telle que f (x + r) = f (x) avec certains choisis au hasard a <N . Il est bien connu que l'algorithme de Shor peut trouver r efficacement sur un ordinateur quantique, alors qu'il est...
Que sait-on de la transition de phase dans les problèmes # P-Complete? Spécifiquement, existe-t-il une transition de phase différente pour # DNF-k-SAT et # CNF-k-SAT? Mise à jour: Comme nous le savons, il y a une transition de phase dans Random k-SAT où la résolution du problème passe de facile à...
Comment peut-on considérer un problème et pourquoi il est probable NP-intermédiaire par opposition à NP-complet? Il est souvent assez simple d'examiner un problème et de dire s'il est probablement NP-complet ou non, mais il me semble beaucoup plus difficile de dire si un problème est...
Je suppose qu'il s'appellerait # P-Space mais je n'ai trouvé qu'un seul article le mentionnant vaguement. Que diriez-vous de la version de comptage des problèmes EXP-TIME-Complete, NEXP-Complete ainsi que EXP-SPACE-Complete? Y a-t-il des travaux antérieurs que l'on peut citer en ce qui concerne...
Supposons que nous ayons un semi-groupe avec les éléments . Notre objectif est de calculer les produits .S = { s 1 , s 2 , … , s n } s i ∘ s i + 1 ∘ ⋯ ∘ s j( S, ∘ )(S,∘)(S,\circ)S= { s1, s2, … , Sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesje∘ si + 1∘ ⋯ ∘ sjsje∘sje+1∘⋯∘sjs_i\circ...
Dans les systèmes de contrôle de version distribués (tels que Mercurial et Git ), il est nécessaire de comparer efficacement les graphiques acycliques dirigés (DAG). Je suis un développeur Mercurial, et nous serions très intéressés d'entendre des travaux théoriques qui discutent de la complexité...
Existe-t-il des problèmes dont la complexité moyenne des cas est la même que leur pire complexité? Quelles sont les propriétés sous-jacentes de ces problèmes qui permettent de réduire le pire des cas au cas
Je m'intéresse à une variation SAT où la formule CNF est monotone (aucune variable n'est niée). Une telle formule est évidemment satisfaisable. Mais disons que le nombre de vraies variables est une mesure de la qualité de notre solution. Nous avons donc le problème suivant: VÉRITABLE MONOTONE 3SAT...
Cette question n'est peut-être pas technique. En tant que locuteur non natif et TA pour la classe d'algorithmes, je me suis toujours demandé ce que signifie gadget dans «gadget de clause» ou «gadget variable». Le dictionnaire dit qu'un gadget est une machine ou un appareil, mais je ne sais pas...
Je travaille dans un laboratoire de neurosciences computationnelles qui quantifie les informations mutuelles entre paires ou groupes de neurones. Récemment, le patron s'est concentré sur la mesure de la "complexité de la dynamique neuronale". En poursuivant cette ligne de recherche, certaines...
Le problème de la partition à 3 cliques est le problème de déterminer si les sommets d'un graphe, disons , peuvent être partitionnés en 3 cliques. Ce problème est NP-difficile par une simple réduction du problème de la colorabilité 3. Il n'est pas difficile de voir que la réponse à ce problème est...
Dana Angluin ( 1987 ; pdf ) définit un modèle d'apprentissage avec des requêtes d'appartenance et des requêtes théoriques (contre-exemples d'une fonction proposée). Elle montre qu'un langage régulier qui est représenté par un DFA minimal de états peut être appris en temps polynomial (où les...
Un théorème de produit direct, de manière informelle, dit que calculer instances d'une fonction est plus difficile que calculer une fois.f fkkkFffFff Les théorèmes typiques du produit direct (par exemple, le lemme XOR de Yao) examinent la complexité du cas moyen et soutiennent (très grossièrement)...
Il a été montré dans l'article "Programmation entière avec un nombre fixe de variables" que les programmations entières avec un nombre constant de contraintes (ou variables) peuvent être résolues polynomialement. Cela vaut-il pour la programmation