+1-315-636-4485
+91 98151-74050 
This quiz contains multiple-choice problems on PSPACE, randomized algorithms, RP and ZPP complexities.
All sets of polynomial questions can be solved by a Turing machine using a polynomial amount of space called
PSPACE
NPSPACE
EXPSPACE
None of the above
PSPACE is strictly the superset of
Regular language
Context-free language
Context-sensitive language
None of the above
Which of the following relates to the switching circuit theorem?
PSPACE=NPSPACE
Alternating Turing machine
Time complexity
None of the above
For which of the following operations is the PSPACE class closed?
Union
Concatenation
Kleene
All of the above
Correct the given order: NL ∈ P ∈ NP ∈ PH ∈ PSPACE
NP ∈ P ∈ NL ∈ PH ∈ PSPACE
NL ∈ PH ∈ NP ∈ P ∈ PSPACE
NL ∈ P ∈ NP ∈ PH ∈ PSPACE
None of the above
All PSPACE problems can be reduced to PSPACE-complete problems. True or false?
True
False
Without needing extra __, we can simulate non-deterministic Turing machines using deterministic Turing machines.
Time
Space
Both time and space
None of the above
The complement of all the problems in PSPACE is
PSPACE
NL
P
All of the above
Which of the following PSPACE can be characterized into?
APTIME
AP
Quantom complexity class
None of the above
A randomized algorithm uses random bits as input to achieve a __ good performance over all possible random bits.
Worst case
Best case
Average case
None of the above
Which of the following are probalistic algorithms?
Las Vegas algorithm
Monte Carlo algorithm
Atlantic City algorithm
All of the above
Which of the following algorithms are probably correct as well as fast?
Las Vegas algorithm
Monte Carlo algorithm
Atlantic City algorithm
All of the above
Which of the following is related to the prisoner’s dilemma?
Cooperative behaviour
Graph theory
All of the above
None of the above
Unix sort command uses __ as its sorting technique.
Quick sort
Bucket sort
Radix sort
Merge sort
A Turing machine has the capability of using randomly generated numbers. True or false?
True
False
