polynomial space
polynomial space 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.
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.
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.
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.
More From encyclopedia.com
Space , Space is the three-dimensional extension in which all things exist and move. Intuitively, it feels that we live in an unchanging space. In this space… Outer Space , The fame of the first achievements in outer space in the 1950s and the high cost of space pro-grams have encouraged a general belief that a new and r… Space-time , space-time, central concept in the theory of relativity that replaces the earlier concepts of space and time as separate absolute entities. In relati… Extravehicular Activity (manned Space Flight) , Space Walks
A space walk, also known as extravehicular activity (EVA), is an activity or maneuver performed by an astronaut outside a spacecraft. Ast… Vehicles , Space vehicles encompass different categories of spacecraft, including satellites ,rockets , space capsules ,space stations , and colonies. In genera… Comics , Comics
In his two volumes Maus: A Survivor's Tale and Maus: A Survivor's Tale II, Art Spiegelman narrates the fate of his parents, a Polish Jewish co…
You Might Also Like
NEARBY TERMS
polynomial space