Overview

polynomial space


Show Summary Details

Quick Reference

A way of characterizing the complexity of an algorithm. If the space complexity (see complexity measure) is polynomially bounded, the algorithm is said to be executable in polynomial space. Many problems for which no polynomial time algorithms have been found, nevertheless can easily be solved in an amount of space bounded by a polynomial in the length of the input.

Formally PSPACE is defined as the class of formal languages that are recognizable in polynomial space. Defining P and NP as the classes of languages recognizable in polynomial time and recognizable in polynomial time on a nondeterministic Turing machine, respectively (see P—NP question), it can be shown that P is a subset of PSPACE and that NP is also a subset of PSPACE. It is not known, however, whether NP= PSPACE although it is conjectured that they are different, i.e. that there exist languages in PSPACE that are not in NP.

NP= PSPACE

Many problems associated with recognizing whether a player of a certain game (like GO) has a forced win from a given position are PSPACE-complete, which is defined in a similar manner to NP-completeness (see P—NP question). This implies that such languages can be recognized in polynomial time only if PSPACE= P Such problems can thus be considered to be even harder than NP-complete problems.

PSPACE= P

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.