Metadata
Author: WikiMatrix
Data
Esperanto[eo]
Multaj penis trovi polinomo-tempajn algoritmojn por ĝi kaj malsukcesis, pro tia ĝi estas larĝe suspektita al esti ekster P. En kontrasto, la primeca provo, kiu estas la decida problemo "ĉu N estas komponigita nombro?", aŭ ekvivalente: "ĉu N estas primo?", aspektas kiel multe pli simpla ol la problemo de reala trovo de faktoroj de N. Aparte, la premieca provo povas esti solvita en polinoma tempo de kvanto de ciferoj de la nombro per la AKS primeca provo.
French[fr]
Beaucoup de personnes ont essayé de trouver des algorithmes en temps polynomial pour cela et ont échoué ; par conséquent, ce problème est largement suspecté d'être également en dehors de P. De manière intéressante, le problème de décision « N est-il un nombre composé ? » (ou de façon équivalente : « N est-il un nombre premier ? ») apparaît comme étant plus facile que le problème consistant à trouver les facteurs de N. Plus précisément, la question ci-dessus peut être résolue en temps polynomial (en nombre n des chiffres de N).