Class RP, ZPP & Complexity - Automata Theory Questions and Answers

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Complexity Classes,Class RP and ZPP”.

1. Which among the following is smallest for n=50
a) 2n2
b) n2+3n+7
c) n3
d) 2n
View Answer

Answer: b
Explanation:
2n2=5000
n2+3n+7=2567
n3=125000
2n=1.13*1015

2. 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
View Answer

Answer: c
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.

3. In order to reduce the run time of a turing machine:
a) we can reduce the number of tapes
b) we can increase the number of tapes
c) use infinite tapes
d) none of the mentioned
View Answer

Answer: b
Explanation: One way to reduce the run time can be to increase the number of tapes. Sometimes, using two tapes can be used to avoid back and forth motions altogether.

4. Which of the following are basic complexity classes for a function f:N->N?
a) Ntime(f)
b) Nspace(f)
c) Space(f)
d) All of the mentioned
View Answer

Answer: d
Explanation: Ntime(f): is a set of languages that can be accepted by a NTM T with non deterministic time complexity function t <=f. In all four cases, the machines are allowed to be multitape TM’s.

5. A function f is called __________ if there exists a TM T so that for any n and any input string of length n, T halts in exactly f(n) moves.
a) Step function
b) Step counting function
c) Inplace functions
d) None of the mentioned
View Answer

Answer: b
Explanation: If f is a step counting function, T is a TM halting in f(n) moves where n is the length of input string.

Note: Join free Sanfoundry classes at Telegram or Youtube

6. Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)
a) O(nf)
b) O(n+f)
c) O(n²f²)
d) None of the mentioned
View Answer

Answer: c
Explanation: Using the encoding function, it is possible to show that if the function f is a step counting function, then the function Cn²(f(n))² is the total number of moves required.

7. Which among the following is false?
If f=O(h) and g=O(k) for f,g,h,k:N->N, then
a) f+g = O(h+k)
b) fg = O(hk)
c) f^g=O(h^k)
d) None of the mentioned
View Answer

Answer: c
Explanation: f,g,h,k are partial functions and each is defined at all but a finite number of points.

8. Which of the following is not correct for ZPP?
a) zero error probabalistic polynomial time
b) it runs in non-polynomial time
c) it returns an answer yes, no or do not know
d) none of the mentioned
View Answer

Answer: b
Explanation: ZPP is zero error probabalistic polynomial time complexity class which run in polynomial time, returns an answer: yes, no or do not know.

9. ZPP is based on ________
a) Probabalistic turing machine
b) Alternative turing machine
c) Quantum turing machine
d) None of the mentioned
View Answer

Answer: a
Explanation: 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.

10. ZPP is exactly equal to the ____________of the classes RP and co-RP.
a) Union
b) Intersection
c) Concatenation
d) Difference
View Answer

Answer: b
Explanation: To prove the following statement, we need to take in note that every problem in RP and co-RP has a Las-Vegas algorithm.

11. Suppose we have a las vegas algorithm C to prove ZPP is contained in RP and co-RP. Run C for double its expected running time.
By Markov’s inequality, the chance that it will answer before we stop is:
a) 1/2
b) 1/4
c) 1/3
d) none of the mentioned
View Answer

Answer: a
Explanation: This means the chance we’ll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm.

12. State true or false:
Statement: ZPP is closed under complement function.
a) true
b) false
View Answer

Answer: a
Explanation: ZPP is said to be closed under complement function i.e. ZPP=co-ZPP.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

« Prev - Automata Theory Questions and Answers – Randomized Algorithm

» Next - Automata Theory Questions and Answers – Applications of NFA

Related Posts:

Recommended Articles: