adplus-dvertising
frame-decoration

Question

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

Answer: (d).All of the mentioned

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Which of the following are basic complexity classes for a function f:N->N?

Similar Questions

Discover Related MCQs

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.

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

Q. Which among the following is false?

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

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

Q. ZPP is based on ________

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

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:

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

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

Q. Diagonalization can be useful in:

Q. Which of the following are undecidable problems?

Q. Which of the following are incorrect options?

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

Q. Which of the following are decidable problems?

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

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

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

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

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.

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