Complexité-théorique difficile de vérifier la valeur de

La fonction de comptage de nombres premiers , rétrogradée , est définie comme le nombre de nombres premiers inférieurs ou égaux à x .$\pi(x)$$x$

Nous pouvons définir un problème de décision à partir de comme suit:$\pi(x)$

Étant donné deux nombres et n , écrits en binaire, décidez si π ( x ) = n .$x$$n$$\pi(x) = n$

Un ami et moi parlions de ce problème un peu plus tôt dans la journée. Il existe un algorithme pseudo-polynomial pour ce problème - il suffit de compter jusqu'à , en utilisant la division d'essai à chaque étape pour voir combien de nombres sont premiers, et vérifier si cela est égal à n . Le problème est également dans PSPACE, puisque l'algorithme que je viens de décrire peut être implémenté pour utiliser uniquement l'espace auxiliaire polynomial.$x$$n$

Cependant, j'ai du mal à trouver un moyen de placer ce problème dans une classe de complexité inférieure. Je ne vois pas comment construire un vérificateur polynomial pour le problème, donc je ne sais pas s'il est en NP, et je ne peux pas penser à un moyen de l'intégrer dans la hiérarchie polynomiale.

Quelle est la classe de complexité la plus appropriée pour ce problème?

Merci!

C'est vraiment un problème ouvert. Je vais esquisser quelques classes dans lesquelles le problème pourrait s'intégrer "naturellement".

Il est difficile de travailler avec votre définition, le problème est difficile à intégrer dans une classe de complexité existante. La langue que vous avez définie est l'intersection des langues et { ( x , n ) | π ( x ) ≥ n } . Donc, si par exemple { ( x , n ) | π ( x ) ≤ n } était dans la classe$\{(x,n)|\pi(x)\leq n\}$$\{(x,n)|\pi(x)\geq n\}$$\{(x,n)|\pi(x)\leq n\}$ alors { ( x , n ) | π ( x ) ≥ n } serait en c o K . Cela rend difficile la caractérisation du langage que vous avez défini, car il faudrait indiquer «l'intersection d'un langage en K avec un langage en c o K » pour donner la limite la plus stricte.$K$$\{(x,n)|\pi(x)\geq n\}$$coK$$K$$coK$

Le problème "Calculer " est un problème dans # P , où # P ⊆ F P S P A C E est la classe de problèmes de la forme "Calculer le nombre de chemins d'acceptation d'une MT polynomiale non déterministe". Il est clair que nous pouvons construire une MT non déterministe qui devine un nombre q ≤ x , puis (avec AKS) tester si q est premier.$\pi(X)$$\#P$$\#P\subseteq FPSPACE$$q \leq x$$q$

Une variante de décision de est P P , qui est la classe de langages de la forme: "Étant donné un polynôme non déterministe TM, au moins la moitié des chemins de calcul acceptent-ils?". Les deux { ( x , n ) | π ( x ) ≤ n } et { ( x , n ) | π ( x ) ≥ n } sont probablement réductibles à un problème dans P $\#P$$PP$$\{(x,n)|\pi(x)\leq n\}$$\{(x,n)|\pi(x)\geq n\}$$PP$ (en faisant un peu de fudging à la MT susmentionnée pour équilibrer le nombre de chemins d'acceptation).

Votre problème est en C = P$_=$ via l'algorithme$\hspace{-0.06 in}\text{,}$

$\;\;\;$devinez de façon non déterministe un entier tel que$\big[$m et un peu$\: 0\leq m < 2^{\lceil \hspace{.02 in}\log_{\hspace{.02 in}2}\hspace{-0.02 in}(x+1)\rceil}\big]$b
$\;\;\;$si x < malors rejeter
$\;\;\;$si b=1alors:
$\;\;\;\;\;$si m < nalors accepter sinon rejeter
$\;\;\;$ autre:
$\;\;\;\;\;$si m est premier alors accepter sinon rejeter

.


En particulier, votre problème est également en PP, car PP est fermé en raison de réductions de table de vérité .

En pratique, vous pouvez obtenir la réponse plus rapidement ou plus lentement :-(

Il existe des approximations assez bonnes pour π (x). Vous calculez donc une telle approximation, et si elle est trop éloignée, vous savez que π (x) ≠ n. Par exemple, si n ≥ x alors je sais que π (x) ≠ n sans rien calculer.

Il existe un algorithme rapide qui détermine si π (x) est pair ou impair, fonctionnant en O (x ^ (1/2)). Vous pouvez exécuter cet algorithme et il peut détecter que la parité de n est incorrecte et vous avez terminé. Il a cinquante chances si n est un entier aléatoire proche de π (x).

À part cela, je ne connais aucune méthode plus rapide que le calcul de π (x). Ce qui est très gênant - si j'écris un programme qui est censé calculer π (10 ^ 25), et que j'obtiens un résultat qui n'est évidemment pas faux, alors il n'y a aucun moyen de vérifier que mon résultat est correct autre que de répéter le calcul. Et vous ne pouvez pas simplement répéter le calcul en utilisant mon programme, vous devez écrire un programme différent, sinon vous ne détecteriez pas si mon programme a des bogues qui lui font calculer une fonction légèrement différente de π (x).

π (x) peut être calculé assez facilement dans environ O (n ^ (2/3)), et plus rapidement avec des mathématiques très profondes.