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

View solution

Q. Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)

View solution

Q. Which among the following is false?

If f=O(h) and g=O(k) for f,g,h,k:N->N, then

View solution

Q. Which of the following is not correct for ZPP?

View solution

Q. ZPP is based on ________

View solution

Q. ZPP is exactly equal to the ____________of the classes RP and co-RP.

View solution

Q. 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:

View solution

Q. State true or false:
Statement: ZPP is closed under complement function.

View solution

Q. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?

View solution

Q. Diagonalization can be useful in:

View solution

Q. Which of the following are undecidable problems?

View solution

Q. Which of the following are incorrect options?

View solution

Q. If a problem has an algorithm to answer it, we call it _________

View solution

Q. Which of the following are decidable problems?

View solution

Q. Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}

View solution

Q. Statement: If L id R.E., L^c needs to be R.E. Is it correct?

View solution

Q. Which of the following is true for The Halting problem?

View solution

Q. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.

View solution

Q. With reference to enumeration of binary strings, the conversion of binary strings to integer is possible by treating the resulting string as a base ____ integer.

View solution

Q. The decision problem is the function from string to ______________

View solution