Explore topic-wise InterviewSolutions in .

This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.

1.

The class PSPACE is closed under the following operations:(a) Union(b) Concatenation(c) Kleene(d) All of the mentioned

Answer» Correct choice is (d) All of the mentioned

For explanation: The closure property of PSPACE class includes :- Union, Concatenation and Kleene operation.
Discussion
2.

Savitch theorem relates to which of the following:(a) PSPACE=NPSPACE(b) Alternating Turing Machine(c) Time complexity(d) None of the mentioned

Answer» Right choice is (a) PSPACE=NPSPACE

To explain: Some important conclusions of Savitch theorem includes:

a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.

b) NL∈L2
Discussion
3.

Complement of all the problems in PSPACE is ________(a) PSPACE(b) NL(c) P(d) All of the mentioned

Answer» Right choice is (a) PSPACE

The explanation: The complement of all the problems in PSPACE are also in PSPACE, meaning co-PSPACE= PSPACE.
Discussion
4.

ZPP is based on ________(a) Probabalistic turing machine(b) Alternative turing machine(c) Quantum turing machine(d) None of the mentioned

Answer» Right option is (a) Probabalistic turing machine

The best I can explain: A probabalistic turing machine is a non deterministic turing machine which randomly chooses between the available transitions at each point according to some probability distribution.
Discussion
5.

The space complexity of a turing machine is undefined if:(a) It is a multitape turing machine(b) If no string of length n causes T to use infinite number of tape squares(c) If some input of length n causes T to loop forever(d) None of the mentioned

Answer» Right choice is (c) If some input of length n causes T to loop forever

The best explanation: If there exists an input string of length n that causes T to use an infinite number of tape squares, the space complexity of the turing machine is undefined.
Discussion