Question

In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time.

(a) O(n)

(b) O(n^1/2)

(c) O(n^k), k∈N

(d) None of the mentioned

This question was addressed to me in an interview.

This is a very interesting question from Non Deterministic Polynomial Time topic in division Intractable Problems of Automata Theory

Answer 1

The correct answer is (c) O(n^k), k∈N

Explanation: The complexity class NP can be defined in terms of NTIME as:

NP=O(n^k) for k ∈N.