J u m p t o c o n t e n t
M a i n m e n u
M a i n m e n u
N a v i g a t i o n
● M a i n p a g e ● C o n t e n t s ● C u r r e n t e v e n t s ● R a n d o m a r t i c l e ● A b o u t W i k i p e d i a ● C o n t a c t u s ● D o n a t e
C o n t r i b u t e
● H e l p ● L e a r n t o e d i t ● C o m m u n i t y p o r t a l ● R e c e n t c h a n g e s ● U p l o a d f i l e
S e a r c h
Search
A p p e a r a n c e
● C r e a t e a c c o u n t ● L o g i n
P e r s o n a l t o o l s
● C r e a t e a c c o u n t ● L o g i n
P a g e s f o r l o g g e d o u t e d i t o r s l e a r n m o r e ● C o n t r i b u t i o n s ● T a l k
( T o p )
1 C o m p l e x i t y c l a s s e s
2 R e l a t i o n w i t h o t h e r c o m p l e x i t y c l a s s e s
T o g g l e R e l a t i o n w i t h o t h e r c o m p l e x i t y c l a s s e s s u b s e c t i o n
2 . 1 D S P A C E
2 . 2 T i m e
3 L i m i t a t i o n s
4 R e f e r e n c e s
5 E x t e r n a l l i n k s
T o g g l e t h e t a b l e o f c o n t e n t s
N S P A C E
8 l a n g u a g e s
● C a t a l à ● D e u t s c h ● E s p a ñ o l ● F r a n ç a i s ● 日 本 語 ● P o r t u g u ê s ● С р п с к и / s r p s k i ● 中 文
E d i t l i n k s
● A r t i c l e ● T a l k
E n g l i s h
● R e a d ● E d i t ● V i e w h i s t o r y
T o o l s
T o o l s
A c t i o n s
● R e a d ● E d i t ● V i e w h i s t o r y
G e n e r a l
● W h a t l i n k s h e r e ● R e l a t e d c h a n g e s ● U p l o a d f i l e ● S p e c i a l p a g e s ● P e r m a n e n t l i n k ● P a g e i n f o r m a t i o n ● C i t e t h i s p a g e ● G e t s h o r t e n e d U R L ● D o w n l o a d Q R c o d e ● W i k i d a t a i t e m
P r i n t / e x p o r t
● D o w n l o a d a s P D F ● P r i n t a b l e v e r s i o n
A p p e a r a n c e
F r o m W i k i p e d i a , t h e f r e e e n c y c l o p e d i a
The measure NSPACE is used to define the complexity class whose solutions can be determined by a non-deterministic Turing machine . The complexity class NSPACE(f n decision problems that can be solved by a non-deterministic Turing machine , M O f n n [1]
Several important complexity classes can be defined in terms of NSPACE . These include:
REG = DSPACE(O 1 )) = NSPACE(O 1 )), where REG is the class of regular languages (nondeterminism does not add power in constant space).
NL O n
CSL = NSPACE(O n context-sensitive languages .
PSPACE = NPSPACE =
⋃
k ∈
N
N S P A C E
(
n
k
)
{\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}
EXPSPACE = NEXPSPACE =
⋃
k ∈
N
N S P A C E
(
2
n
k
)
{\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}
The Immerman–Szelepcsényi theorem states that NSPACE(s n s n n
A further generalization is ASPACE, defined with alternating Turing machines .
Relation with other complexity classes [ edit ]
NSPACE is the non-deterministic counterpart of DSPACE , the class of memory space on a deterministic Turing machine . First by definition, then by Savitch's theorem , we have that:
D S P A C E
[
s (
n )
]
⊆
N S P A C E
[
s (
n )
]
⊆
D S P A C E
[
(
s (
n )
)
2
]
.
{\displaystyle {\mathsf {DSPACE}}[s(n )]\subseteq {\mathsf {NSPACE}}[s(n )]\subseteq {\mathsf {DSPACE}}[(s(n ))^{2}].}
NSPACE can also be used to determine the time complexity of a deterministic Turing machine by the following theorem:
If a language L S n S n n C L O C S n [2]
Limitations [ edit ]
The measure of space complexity in terms of DSPACE is useful because it represents the total amount of memory that an actual computer would need to solve a given computational problem with a given algorithm . The reason is that DSPACE describes the space complexity used by deterministic Turing machines , which can represent actual computers. On the other hand, NSPACE describes the space complexity of non-deterministic Turing machines , which are not useful when trying to represent actual computers. For this reason, NSPACE is limited in its usefulness to real-world applications.
References [ edit ]
^ Goddard, Wayne (2008). Introducing the Theory of Computation . Jones and Bartlett Publishers, Inc. p. 183. ISBN 978-0-7637-4125-9
External links [ edit ]
R e t r i e v e d f r o m " https://en.wikipedia.org/w/index.php?title=NSPACE&oldid=1010766202 " C a t e g o r i e s : ● C o m p l e x i t y c l a s s e s ● C o m p u t a t i o n a l r e s o u r c e s
● T h i s p a g e w a s l a s t e d i t e d o n 7 M a r c h 2 0 2 1 , a t 0 5 : 4 7 ( U T C ) . ● T e x t i s a v a i l a b l e u n d e r t h e C r e a t i v e C o m m o n s A t t r i b u t i o n - S h a r e A l i k e L i c e n s e 4 . 0 ;
a d d i t i o n a l t e r m s m a y a p p l y . B y u s i n g t h i s s i t e , y o u a g r e e t o t h e T e r m s o f U s e a n d P r i v a c y P o l i c y . W i k i p e d i a ® i s a r e g i s t e r e d t r a d e m a r k o f t h e W i k i m e d i a F o u n d a t i o n , I n c . , a n o n - p r o f i t o r g a n i z a t i o n . ● P r i v a c y p o l i c y ● A b o u t W i k i p e d i a ● D i s c l a i m e r s ● C o n t a c t W i k i p e d i a ● C o d e o f C o n d u c t ● D e v e l o p e r s ● S t a t i s t i c s ● C o o k i e s t a t e m e n t ● M o b i l e v i e w
![{\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecd4ae2f63770c1eb464eab1a65c457990883b00)