Definitions

NESPACE

NESPACE

In computational complexity theory, the complexity class NESPACE is the set of decision problems that can be solved by a non-deterministic Turing machine in space O(2n). If ESPACE is defined as the set of decision problems that can be solved by a deterministic Turing machine in space O(2n), then ESPACE is a subset of NESPACE. However, if it is instead defined as the set of decision problems that can be solved by a deterministic Turing machine in space 2O(n), then NESPACE is a proper subset of ESPACE, by Savitch's theorem and the space hierarchy theorem.

In any case, the closure of either class under polynomial-time many-one reductions is EXPSPACE.

Search another word or see NESPACEon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;