Automata Theory Class Rp Zpp Online Exam Quiz
Automata Theory Class Rp Zpp GK Quiz. Question and Answers related to Automata Theory Class Rp Zpp. MCQ (Multiple Choice Questions with answers about Automata Theory Class Rp Zpp
Which among the following is smallest for n=50
Options
A : 2n2
B : n2+3n+7
C : n3
D : 2n
The space complexity of a turing machine is undefined if:
Options
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
Which of the following are basic complexity classes for a function f:N->N?
Options
A : Ntime(f)
B : Nspace(f)
C : Space(f)
D : All of the mentioned
Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)
Options
A : O(nf)
B : O(n+f)
C : O(n2f2)
D : None of the mentioned
ZPP is based on ________
Options
A : Probabalistic turing machine
B : Alternative turing machine
C : Quantum turing machine
D : None of the mentioned
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.
Options
A : Step function
B : Step counting function
C : Inplace functions
D : None of the mentioned
ZPP is exactly equal to the ____________of the classes RP and co-RP.
Options
A : Union
B : Intersection
C : Concatenation
D : Difference
Which of the following is not correct for ZPP?
Options
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
Chemical Engineering Basics - Part 1 more Online Exam Quiz
Automata Theory Campus Interviews
Automata Theory Cfl Closure Properties
Automata Theory Cfl Substitution Theorem
Automata Theory Chomsky Normal Form
Automata Theory Construction Yield Parse Tree
Automata Theory Context Free Grammar Derivations Definitions
Automata Theory Converting Regular Expressions Automata