gs gs101 Other Classes Of Problems - Class RP, ZPP and Complexity - Quiz No.1
gs gs101 Automata Theory Quiz
This quiz belongs to book/course code gs gs101 Automata Theory of gs organization. We have 92 quizzes available related to the book/course Automata Theory. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Other Classes Of Problems. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: Which among the following is smallest for n=50
2n2
n2+3n+7
n3
2n
Question 2: The space complexity of a turing machine is undefined if:
It is a multitape turing machine
If no string of length n causes T to use infinite number of tape squares
If some input of length n causes T to loop forever
None of the mentioned
Question 3: In order to reduce the run time of a turing machine:
we can reduce the number of tapes
we can increase the number of tapes
use infinite tapes
none of the mentioned
Question 4: Which of the following are basic complexity classes for a function f:N->N?
Ntime(f)
Nspace(f)
Space(f)
All of the mentioned
Question 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.
Step function
Step counting function
Inplace functions
None of the mentioned
Question 6: Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)
O(nf)
O(n+f)
O(n2f2)
None of the mentioned
Question 7: Which among the following is false?
If f=O(h) and g=O(k) for f,g,h,k:N->N, then
If f=O(h) and g=O(k) for f,g,h,k:N->N, then
f+g = O(h+k)
fg = O(hk)
fg=O(hk)
None of the mentioned
Question 8: Which of the following is not correct for ZPP?
zero error probabalistic polynomial time
it runs in non-polynomial time
it returns an answer yes, no or do not know
none of the mentioned
Question 9: ZPP is based on ________
Probabalistic turing machine
Alternative turing machine
Quantum turing machine
None of the mentioned
Question 10: ZPP is exactly equal to the ____________of the classes RP and co-RP.
Union
Intersection
Concatenation
Difference
Online Quizzes of gs101 Automata Theory
Other Classes Of Problems - Randomized Algorithm - Quiz No.1
gs gs101
Automata Theory Online Quizzes
Push Down Automata - DPDA and Ambiguous Grammars - Quiz No.1
gs gs101
Automata Theory Online Quizzes
