Space complexity classes (PSPACE, L, NL) MCQs

By: Prof. Dr. Fazal Rehman | 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.  

• Theory of Automata MCQs
• Finite Automata MCQs
  • Deterministic Finite Automata (DFA) MCQs
  • Non-deterministic Finite Automata (NFA) MCQs
  • Equivalence of DFA and NFA MCQs
  • Minimization of DFA MCQs
• Regular Languages
  • Regular Expression MCQs
  • Properties of regular languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for regular languages MCQs
• Context-Free Grammars (CFG)
  • CFG MCQs
  • Parse trees and derivations MCQs
  • Ambiguity in grammars MCQs
• Pushdown Automata (PDA) MCQs
  • Deterministic PDA vs Non-deterministic PDA MCQs
  • Relationship between PDA and context-free languages MCQs
• Context-Free Languages MCQs
  • Properties of context-free languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for context-free languages MCQs
• Turing Machines MCQs
  • Turing machine as a language recognizer and transducer MCQs
• Decidability and Undecidability MCQs
  • Decidable languages and problems MCQs
  • Undecidable languages and problems MCQs
  • Rice’s theorem MCQs
  • Reduction techniques MCQs
• Computational Complexity MCQs
  • Time complexity classes (P, NP, NP-complete, NP-hard) MCQs
  • Space complexity classes (PSPACE, L, NL) MCQs
  • Polynomial time reductions MCQs
• Advanced Topics in Automata Theory
  • Linear-bounded automata MCQs
  • Context-sensitive grammars and languages MCQs
  • Chomsky hierarchy MCQs
  • Introduction to quantum automata MCQs
• Applications of Automata Theory MCQs