Complexité en espace

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely. This includes the memory space used by its inputs, called input space, and any other (auxiliary) memory it uses during execution, which is called auxiliary space. Similar to time complexity, space complexity is often expressed asymptotically in big O notation, such as etc., where n is a characteristic of the input influencing space complexity. Analogously to time complexity classes DTIME(f(n)) and NTIME(f(n)), the complexity classes DSPACE(f(n)) and NSPACE(f(n)) are the sets of languages that are decidable by deterministic (respectively, non-deterministic) Turing machines that use space. The complexity classes PSPACE and NPSPACE allow to be any polynomial, analogously to P and NP. That is, and The space hierarchy theorem states that, for all space-constructible functions there exists a problem that can be solved by a machine with memory space, but cannot be solved by a machine with asymptotically less than space. The following containments between complexity classes hold. Furthermore, Savitch's theorem gives the reverse containment that if As a direct corollary, This result is surprising because it suggests that non-determinism can reduce the space necessary to solve a problem only by a small amount. In contrast, the exponential time hypothesis conjectures that for time complexity, there can be an exponential gap between deterministic and non-deterministic complexity. The Immerman–Szelepcsényi theorem states that, again for is closed under complementation. This shows another qualitative difference between time and space complexity classes, as nondeterministic time complexity classes are not believed to be closed under complementation; for instance, it is conjectured that NP ≠ co-NP.