Questions en théorie des nombres
Nous savons que la fonction exponentielle sur les nombres naturels n'est pas calculable en temps polynomial, car la taille de la sortie n'est pas polynomiale dans la taille des entrées.exp( x , y) = xyexp(x,y)=xy\exp(x,y) = x^y Est-ce la raison principale de la difficulté de calculer la fonction...
Récemment, Gil Kalai et Dick Lipton ont tous deux écrit un bel article sur une hypothèse intéressante proposée par Peter Sarnak, expert en théorie des nombres et Hypothèse de Riemann. Conjecture. Soit la fonction de Möbius . Supposons que soit une fonction avec entrée sous la forme d'une...
Considérez le problème de comptage suivant (ou le problème de décision associé): Étant donné deux entiers positifs codés en binaire, calculez leur plus grand commun diviseur (gcd). Quelle est la plus petite classe de complexité dans laquelle ce problème est contenu? Pouvez-vous fournir une...
Tout nombre naturel peut être considéré comme une séquence de bits, donc la saisie d'un nombre naturel est la même que la saisie d'une séquence 0-1, donc des problèmes NP-complets avec des entrées naturelles existent évidemment. Mais y a-t-il des problèmes naturels, c'est-à-dire ceux qui...
Étant donné un entier de longueur n bits, est-il difficile de produire le nombre de facteurs premiers (ou alternativement le nombre de facteurs) de N ?NNNnnnNNN Si nous connaissions la factorisation première de , ce serait facile. Cependant, si nous connaissions le nombre de facteurs premiers ou...
Que sait-on de la complexité de calcul de la factorisation d'entiers dans des champs de nombres généraux? Plus précisement: Sur les entiers, nous représentons des entiers via leurs extensions binaires. Quelles sont les représentations analogues d'entiers dans des champs numériques généraux? Est-il...
Est un algorithme déterministe à temps polynomial connu pour le problème suivant: Entrée: un nombre naturel (en encodage binaire)nnn Sortie: un nombre premier .p > np>np > n (Selon une liste de problèmes ouverts par Leonard Adleman, le problème était ouvert en 1995.)
Quelles implications une preuve de la conjecture abc aurait-elle pour tcs?
La première étape de l'algorithme de test de primalité AKS consiste à vérifier si le numéro d'entrée est une puissance parfaite. Il semble que ce soit un fait bien connu de la théorie des nombres, car l'article ne l'explique pas en détail. Quelqu'un peut-il me dire comment faire cela en temps...
Rappelons le nombre de nombres premiers est la fonction de décompte des nombres premiers . Par "PRIMES in P", le calcul est en #P. Le problème # P-est-il complet? Ou, peut-être, il y a une raison complexe de croire que ce problème n'est pas # P-complet? π(n)π(n)\pi(n)≤n≤n\le nπ ( n )π(n)π(n)\pi(n)...
Wikipedia fournit des exemples de problèmes où la version de comptage est difficile, alors que la version de décision est facile. Certains d'entre eux comptent des appariements parfaits, comptant le nombre de solutions à 222 -SAT et le nombre de tri topologiques. Existe-t-il d'autres classes...
Je suis intéressé par la complexité de la résolution d'équations linéaires modulo k , pour k arbitraire (et avec un intérêt particulier pour les puissances premières), en particulier: Problème. Pour un système donné de équations linéaires dans n modules inconnus k , existe-t-il des...
Dans son article de 1995 Algorithmes à temps polynomial pour la factorisation principale et les logarithmes discrets sur un ordinateur quantique , Peter W. Shor discute d'une amélioration de la partie recherche d'ordres de son algorithme de factorisation. Les sorties algorithme standard , un...
Je me demandais s'il y avait une bonne bibliographie des tentatives d'enquêter sur la conjecture de Collatz comme grammaire formelle? (ou toute autre tentative dans la communauté CS pour faire face à cette classe de phénomènes génératifs et leurs propriétés
Je m'intéresse au problème "le plus proche" (et "le plus complexe") de la conjecture de Collatz qui a été résolue avec succès (ce que Erdos a dit fameusement "les mathématiques ne sont pas encore mûres pour de tels problèmes"). Il a été prouvé qu'une classe de problèmes "de type Collatz" est...
Quelle est la complexité de décider si un intervalle des nombres naturels contient un nombre premier? Une variante du tamis d'Ératosthène donne un algorithme O~(L)O~(L)\tilde O(L) , où LLL est la longueur de l'intervalle et ∼∼\sim cache les facteurs poly-logarithmiques au point de départ de...
D'après les commentaires sur une de mes questions sur mathoverflow je le sentiment que la question concernant GCD étant en par rapport à P est semblable à la question concernant Integer factorisation être dans P par rapport à N P .N CNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}N PNP\mathsf{NP} Y at - il...
'Étant donné a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , y a-t-il x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by=cax2+by=cax^2+by=c ' est NPNP\mathsf{NP} -complet. À quelle classe de complexité «Étant donné a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , y a-t-il x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by2=cax2+by2=cax^2+by^2=c...
Considérez le problème de test d'appartenance au sous-groupe abelian suivant . Contributions: Un groupe abélien fini G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} avec arbitrairement grand .didid_i Un générateur de jeu d'un sous - groupe...
aaabbbaaabbbaaabbbO(mlogmloglogm)O(mlogmloglogm)O(m\log m\log\log m)mmmmax{a,b}max{a,b}\max\{a,b\}Ω(mlogmloglogm)Ω(mlogmloglogm)\Omega(m\log m\log\log m) la limite inférieure de ce problème? Merci et salutations, et désolé si c'est une question aussi