SC (complexité)

En informatique théorique, plus précisément en théorie de la complexité, SC est la classe de complexité des problèmes de décision, décidés par un algorithme en temps polynomial et en espace polylogarithmique.

Temps polynomial

Cela signifie que le temps d'exécution de l'algorithme est limité par un polynôme en fonction de la taille de l'entrée. En d'autres termes, un algorithme en temps polynomial peut résoudre un problème de taille ${\displaystyle n}$ en un temps ${\displaystyle O(n^{k})}$, où ${\displaystyle k}$ est une constante

Espace polylogarithmique

Cela indique que la quantité d'espace (mémoire) utilisée par l'algorithme est limitée à un polynôme logarithmique de la taille de l'entrée. Autrement dit, l'espace utilisé par l'algorithme est ${\displaystyle O(log(n)^{k})}$, où est une constante et ${\displaystyle n}$ est la taille de l'entrée.

Les caractéristiques de SC

La classe SC est une classe de décision, ce qui signifie que les problèmes qui lui appartiennent ont une réponse binaire, généralement "oui" ou "non". Ces problèmes sont caractérisés par leur capacité à être résolus par un algorithme qui prend une décision finale sur la validité d'une proposition donnée, dans un cadre de complexité bien défini. SC se situe dans un espace théorique spécifique entre deux autres classes de complexité bien connues, P et NP. D'une part, P regroupe les problèmes qui peuvent être résolus en temps polynomial, c'est-à-dire avec un algorithme dont le temps d'exécution est borné par un polynôme de la taille de l'entrée.

D'autre part, NP inclut les problèmes dont les solutions peuvent être vérifiées en temps polynomial, bien que leur recherche puisse être difficile ou non réalisable en temps polynomial.

Cependant, la classe SC impose une contrainte supplémentaire par rapport à ces deux classes, en ce sens qu'elle restreint non seulement le temps d'exécution à une complexité polynomiale, mais elle impose aussi une limitation sur l'espace utilisé par l'algorithme. Les algorithmes qui résolvent les problèmes de SC doivent fonctionner avec un espace polylogarithmique, c'est-à-dire que la quantité de mémoire utilisée par l'algorithme est proportionnelle à un polynôme en fonction du logarithme de la taille de l'entrée.

Ce critère rend SC encore plus restrictive que P, car bien que les problèmes dans SC soient résolus en temps polynomial, la mémoire nécessaire pour le faire est beaucoup plus limitée.

Note et Référence

• Stanford - Théorie de la complexité computationnelle[1]
• Herz und Kreislauf[2]

Références

1. Walter Dean, « Computational Complexity Theory », dans The Stanford Encyclopedia of Philosophy, Metaphysics Research Lab, Stanford University, 2021 (lire en ligne)
2. (en) « Herz und Kreislauf », sur Springer (consulté le 29 décembre 2024)