gs gs101 Other Classes Of Problems - PSPACE - Quiz No.1
gs gs101 Automata Theory Quiz
This quiz belongs to book/course code gs gs101 Automata Theory of gs organization. We have 92 quizzes available related to the book/course Automata Theory. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Other Classes Of Problems. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:
PSPACE
NPSPACE
EXPSPACE
None of the mentioned
Question 2: PSPACE is strictly the super set of:
Regular language
Context free language
Context Sensitive Language
None of the mentioned
Question 3: Savitch theorem relates to which of the following:
PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.
NL∈L2
Time complexity
None of the mentioned
Question 4: The class PSPACE is closed under the following operations:
Union
Concatenation
Kleene
All of the mentioned
Question 5: Correct the given order:
NL∈ P∈ NP∈ PH∈ PSPACE
NL∈ P∈ NP∈ PH∈ PSPACE
NP∈ P∈ NL∈ PH∈ PSPACE
NL∈ PH∈ NP∈ P∈ PSPACE
NL∈ P∈ NP∈ PH∈ PSPACE
None of the mentioned
Question 6: NL ∈ PSPACE ∈ EXPSPACE
The given relation involves which of the following theorems?
The given relation involves which of the following theorems?
Space hierarchy theorem
Savitch’s theorem
Space hierarchy and Savitch’s theorems
None of the mentioned
Question 8: Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.
time
space
both time and space
none of the mentioned
Question 9: Complement of all the problems in PSPACE is ________
PSPACE
NL
P
All of the mentioned
Question 10: Which of the following PSPACE can be characterized into?
APTIME
AP
Quantom complexity class
None of the mentioned
Online Quizzes of gs101 Automata Theory
Other Classes Of Problems - Randomized Algorithm - Quiz No.1
gs gs101
Automata Theory Online Quizzes
Push Down Automata - DPDA and Ambiguous Grammars - Quiz No.1
gs gs101
Automata Theory Online Quizzes
