EXPSPACE

format_list_bulleted Contenido keyboard_arrow_down
ImprimirCitar

In computational complexity theory, the complexity class EXPSPACE is the set of decision problems that can be solved with a deterministic Turing machine in space O(2p(n)), where p(n) is a polynomial function over n . According to Savitch's Theorem, this class is the same as that considered by non-deterministic Turing machines. When constraining p(n) as a linear function, the resulting class is called ESPACE.

In DSPACE terms,

EXPSPACE= k한 한 NDSPACE(2nk){displaystyle {mbox{EXPSPACE}}=bigcup _{kin mathbb {N}}}{mbox{DSPACE}}(2^{n^{k}}}})}

The complexity class EXPSPACE-complete is the class of problems that are in EXPSPACE such that every problem in EXPSPACE has a polynomial transformation to every problem in EXPSPACE-complete. In other words, there is an algorithm that works in polynomial time that transforms the instances of one problem into the instances of another with the same answer. The EXPSPACE-complete set can be seen as the set of the most difficult EXPSPACE problems.

EXPSPACE strictly contains the PSPACE, NP-complete, NP, and P classes and is believed to strictly contain the EXPTIME set as well.

An example of a problem in EXPSPACE-complete is deciding whether two regular expressions represent different languages, when the regular operators used are union, concatenation, Kleene closure (zero or more copies of an expression), and the square (two copies of an expression).

If the Kleene closure is not included, the problem is NEXPTIME-complete, which is like EXPTIME-complete, except that it is defined according to non-deterministic Turing machines.

In 1980, L. Berman showed that the problem of checking or falsifying any first-order expression over real numbers that only uses addition and comparison (but not multiplication) is in EXPSPACE.

Contenido relacionado

Msn messenger

MSN Messenger was an instant messaging program created by Microsoft in 1999 and discontinued in 2005 due to its replacement by Windows Live Messenger, and now...

GNU GRUB

GNU GRUB is a multi-boot loader, developed by the GNU project that allows us to choose which Operating System to boot from those...

Haskell curry

Haskell Brooks Curry was an American mathematician and logician. Born in Millis, Massachusetts, he was educated at Harvard University and received a Ph.D. in...
Más resultados...
Tamaño del texto:
undoredo
format_boldformat_italicformat_underlinedstrikethrough_ssuperscriptsubscriptlink
save