human
Veuillez expliquer ce qu'est un "problème de calcul"
gpt
En informatique théorique, un problème de calcul est un problème qui peut être résolu par un algorithme. Par exemple, le problème de la factorisation
est un problème de calcul. Un problème de calcul peut être considéré comme un ensemble d'instances ou de cas avec un ensemble, éventuellement vide, de solutions pour chaque instance/cas. Par exemple, dans le problème de factorisation, les instances sont les entiers n et les solutions sont les nombres premiers p qui sont les facteurs premiers non triviaux de n.
Les problèmes de calcul sont l'un des principaux objets d'étude en informatique théorique. Le domaine de la théorie de la complexité computationnelle tente de déterminer la quantité de ressources (complexité computationnelle) que la résolution d'un problème donné nécessitera et d'expliquer pourquoi certains problèmes sont insolubles ou indécidables. Les problèmes de calcul appartiennent à des classes de complexité qui définissent largement les ressources (par exemple, le temps, l'espace/mémoire, l'énergie, la profondeur du circuit) nécessaires pour les calculer (résoudre) avec diverses machines abstraites. Par exemple, la classe de complexité P pour les machines classiques, et BQP pour les machines quantiques.
Il est typique de nombreux problèmes de représenter à la fois les instances et les solutions par des chaînes binaires, à savoir des éléments de {0, 1}*. [a] Par exemple, les nombres peuvent être représentés sous forme de chaînes binaires en utilisant un codage binaire.