Automata Theory Questions and Answers – Class RP and ZPP, Complexity

«
»

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
advertisement

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.
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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.
advertisement

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(n2f2)
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 Cn2(f(n))2 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) fg=O(hk)
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.
advertisement

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.
advertisement

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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.