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 mentionedI got this question during an online interview.Question is taken from Class RP and ZPP,Complexity in division Other Classes Of Problems of Automata Theory

The space complexity of a turing machine is undefined if:(a) It is a m

1.	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 mentionedI got this question during an online interview.Question is taken from Class RP and ZPP,Complexity in division Other Classes Of Problems of Automata Theory
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

No Comment Found

Related InterviewSolutions

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 mentionedI have been asked this question in semester exam.This is a very interesting question from Class RP and ZPP,Complexity topic in chapter Other Classes Of Problems of Automata Theory
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 mentionedI have been asked this question in exam.Query is from Class RP and ZPP,Complexity in section Other Classes Of Problems of Automata Theory
Which of the following algorithms are probably correct as well as fast?(a) Las Vegas Algorithm(b) Monte Carlo Algorithm(c) Atlantic City Algorithm(d) All of the mentionedI had been asked this question in an internship interview.Enquiry is from Randomized Algorithm topic in section Other Classes Of Problems of Automata Theory
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 mentionedI had been asked this question in an online interview.Question is taken from Class RP and ZPP,Complexity in division Other Classes Of Problems of Automata Theory
State true or false:Statement: A turing machine has the capability of using randomly ‘generated’ numbers.(a) Statement: A turing machine has the capability of using randomly ‘generated’ numbers.(b) true(c) falseThis question was addressed to me at a job interview.This key question is from Randomized Algorithm topic in chapter Other Classes Of Problems of Automata Theory
Which of the following are probalistic algorithms?(a) Las Vegas Algorithm(b) Monte Carlo Algorithm(c) Atlantic City Algorithm(d) All of the mentionedThe question was asked in an online quiz.This interesting question is from Randomized Algorithm topic in division Other Classes Of Problems of Automata Theory
Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.(a) time(b) space(c) both time and space(d) none of the mentionedThis question was addressed to me in an internship interview.The query is from PSPACE topic in division Other Classes Of Problems of Automata Theory
Which among the following is smallest for n=50(a) 2n2(b) n2+3n+7(c) n3(d) 2nThis question was posed to me at a job interview.Enquiry is from Class RP and ZPP,Complexity topic in portion Other Classes Of Problems of Automata Theory
A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.(a) worst case(b) best case(c) average case(d) none of the mentionedThis question was posed to me in an online interview.The query is from Randomized Algorithm in portion Other Classes Of Problems of Automata Theory
Complement of all the problems in PSPACE is ________(a) PSPACE(b) NL(c) P(d) All of the mentionedI had been asked this question during an interview for a job.I need to ask this question from PSPACE in division Other Classes Of Problems of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment