L' hypothèse de Riemann vieille de plus d'un siècle et demi a des implications profondes en mathématiques et un grand édifice de la théorie mathématique est maintenant prouvé conditionnellement sur elle et de nombreuses variantes. Je suis récemment tombé sur une référence à un résultat conditionnel...
Ma question concerne les algorithmes quantiques pour les calculs QED (électrodynamique quantique) liés aux constantes de structure fine. De tels calculs (comme on m'a expliqué) revient à calculer des séries de type Taylor où α est la constante de structure fine (autour de 1/137) et c k est la...
Dans l'article de 1965 « Sur la complexité de calcul des algorithmes » de Hartmanis et Stearns, les auteurs supposent que si une machine de Turing en temps réel calcule le nombre réel dans, par exemple, la base 10, alors est soit un nombre rationnel soit un numéro transcendantal.rrrrrr Existe-t-il...
La complexité de la preuve est l'un des domaines les plus élémentaires de la théorie de la complexité informatique. Un objectif ultime de ce domaine est de prouver , c'est-à-dire que tout prouveur ne peut pas fournir une preuve d'insatisfiabilité d'une formule d'entrée donnée. NP≠ c o...
Le problème d'isomorphisme des graphes est l'un des problèmes les plus anciens qui ont résisté à la classification en problèmes complets ou . Nous avons des preuves qu'il ne peut pas être complet. Premièrement, l'isomorphisme du graphe ne peut être complet en que si la hiérarchie polynomiale [1]...
Suite aux questions équivalentes concernant NP-Completeness (voir la question de poids et la question dirigée ), je me demandais comment les problèmes paramétrés sont affectés par ces attributs. Quels problèmes de graphes durs sont W [ 1 ] -Dur sur les graphes dirigés, mais les paramètres fixes...
Les problèmes ont été, dans leur ensemble, classés, grâce à la complexité informatique. Mais, dans les équations différentielles, est-il possible de classer les équations différentielles en fonction de leur structure de calcul? Par exemple, si une équation non homogène du premier ordre est...
Étant donné deux permutations et h sur n éléments (c'est-à-dire les membres de S n ), quelle est la complexité du calcul de l'ordre du sous-groupe généré par g , h ? Ou tout simplement de décider si le sous-groupe est d'ordre n ! (c'est-à-dire, tout S n
tttttt Θ ( journaln )Θ(Journaln)\Theta(\log n)tttΘ ( t + logt ⋅ logn )Θ(t+Journalt⋅Journaln)\Theta(t + \log t \cdot \log n) FFfFFfcccFFftttΩ ( t ⋅ ( c√- journaln ) )Ω(t⋅(c-Journaln))\Omega(t \cdot (\sqrt{c} - \log n)) Je ne connais aucun autre résultat général positif sur le problème de la...
Soit k > 0k>0k>0 une constante fixe. Etant donné un entier nnn , nous voulons construire une permutation σ∈ Snσ∈Sn\sigma \in S_n telle que: La construction utilise un temps et un espace constants (c'est-à-dire que le prétraitement prend un temps et un espace constants). Nous pouvons utiliser...
Je me demande s'il peut exister un moyen de donner une sorte de "forme normale" aux arbres de décision binaires (BDT) de manière maniable. Plus précisément: un BDT est un arbre avec des nœuds internes étiquetés par des variables booléennes et des feuilles étiquetées par ou . Un BDT représente une...
Considérez le problème suivant: Étant donné une matrice nous voulons optimiser le nombre d'additions dans l'algorithme de multiplication pour calculer v ↦ M v .MMMv ↦ Mvv↦Mvv \mapsto Mv Je trouve ce problème intéressant en raison de ses liens avec la complexité de la multiplication matricielle (ce...
Il est bien connu que certaines catégories de NP -Problèmes Ont dichotomie théorèmes, qui garantit que toutes les tâches de la classe est soit NP -complete ou est en P . Le résultat le plus connu est le théorème de dichotomie de Schaefer , ainsi qu'un certain nombre de généralisations. Je crois...
Le terme suivant (en utilisant les index bruijn): BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0))))))))) Lorsqu'il est appliqué à un numéro d'église, il prend Nrapidement sa forme normale dans plusieurs évaluateurs existants, y compris...
Existe-t-il des exemples naturels connus de problèmes d'optimisation pour lesquels il est beaucoup plus facile de produire une solution optimale que d'évaluer la qualité d'une solution candidate donnée? Par souci de concrétisation, nous pouvons considérer les problèmes d'optimisation résolubles en...
Je souhaite réduire -Clique en SAT sans agrandir l'instance.kkk La clique est en NP, elle peut donc être réduite à SAT en utilisant l'espace logarithmique. La réduction simple des manuels de Garey / Johnson fait exploser l'instance à la taille cubique . Cependant, -Clique est en P pour chaque fixe...
Soit un polynôme symétrique , c'est-à-dire un polynôme tel que pour tous les et toutes les permutations . Pour plus de commodité, nous pouvons supposer que est un champ fini, pour éviter de résoudre les problèmes avec le modèle de calcul. f ( x ) = f ( σ ( x ) ) x ∈ K n σ ∈ S n KF: Kn→...
L'inclusion inverse est évidente, tout comme le fait que tout langage NP auto-réductible dans BPP l'est également dans RP. Est-ce également connu pour les langages NP non
Permettez à une machine de Turing probabiliste d'avoir accès à une pièce de monnaie injuste qui génère des probabilités (les flips sont indépendants). Définissez comme la classe de langages reconnaissable par une telle machine en temps polynomial. Il s'agit d'un exercice standard pour prouver que:B...
Soit HA L TnHALTnHALT_n la chaîne de longueur 2n2n2^n correspondant à la table de vérité du problème d'arrêt pour les entrées de longueur nnn . Si la séquence des complexités de Kolmogorov K( HA L Tn)K(HALTn)K(HALT_n) était O ( 1 )O(1)O(1) , alors l'une des chaînes de conseil serait utilisée...