Space complexity classes (PSPACE, L, NL) MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 23, 2024

MCQs on Space Complexity Classes
Which of the following complexity classes deals specifically with the space used by algorithms?

A) P
B) NP
C) PSPACE
D) EXPTIME
Answer: C) PSPACE

What does the PSPACE complexity class encompass?

A) Problems solvable in polynomial time
B) Problems solvable in polynomial space
C) Problems solvable in exponential time
D) Problems solvable in exponential space
Answer: B) Problems solvable in polynomial space

Which of the following statements about PSPACE is true?

A) PSPACE is a subset of NP.
B) PSPACE is equivalent to P.
C) PSPACE is closed under complementation.
D) PSPACE contains problems that can be solved using polynomial time.
Answer: C) PSPACE is closed under complementation.

Which space complexity class is defined as the set of problems solvable using logarithmic space on a deterministic Turing machine?

A) P
B) L
C) NL
D) PSPACE
Answer: B) L

True or False: Every problem in PSPACE can also be solved in polynomial time.

A) True
B) False
Answer: B) False

Which space complexity class is characterized by problems that can be solved using polynomial space on a non-deterministic Turing machine?

A) PSPACE
B) L
C) NPSPACE
D) NL
Answer: C) NPSPACE

Which of the following is a key property of the NL (Logarithmic Space) complexity class?

A) NL is closed under complementation.
B) NL is a subset of PSPACE.
C) NL is equivalent to NP.
D) NL contains only decidable problems.
Answer: A) NL is closed under complementation.

In the context of space complexity, what does the class L (Logarithmic Space) encompass?

A) Problems solvable in polynomial space
B) Problems solvable in linear space
C) Problems solvable in exponential time
D) Problems solvable in constant space
Answer: D) Problems solvable in constant space

Which space complexity class is associated with problems that can be verified in polynomial space?

A) PSPACE
B) L
C) NL
D) NPSPACE
Answer: D) NPSPACE

Which statement accurately describes the relationship between space complexity classes?

A) PSPACE is strictly contained within L.
B) L is a subset of PSPACE.
C) NL is equivalent to NPSPACE.
D) PSPACE equals NPSPACE.
Answer: B) L is a subset of PSPACE.

 

Related Posts: