SC (complexité)

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.

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

• Portail de l'informatique théorique