PSPACE, Randomized Algorithms, RP and ZPP Complexities

This quiz contains multiple-choice problems on PSPACE, randomized algorithms, RP and ZPP complexities.

Start Quiz

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

Quiz/Test Summary
Title: PSPACE, Randomized Algorithms, RP and ZPP Complexities
Questions: 15
Contributed by:
Ivan