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

View solution

Q. Which of the following can be used to define NP complexity class?

View solution

Q. Which of the following are not in NP?

View solution

Q. Which of the following does not belong to the closure properties of NP class?

View solution

Q. Which of the given problems are NP-complete?

View solution

Q. Which of the following problems do not belong to Karp’s 21 NP-complete problems?

View solution

Q. Which of the following problems were reduced to Knapsack?

View solution

Q. An exact cover problem can be represented using:

View solution

Q. For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?

View solution

Q. Hamilton circuit problem can have the following version/s as per the input graph:

View solution

Q. Hamilton Circuit problem is a special case of ____________

View solution

Q. Which of the following cannot solve Hamilton Circuit problem?

View solution

Q. State true or false:
Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.

View solution

Q. Fibonacci number falls in the category of _________ combinatorics.

View solution

Q. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:

View solution

Q. PSPACE is strictly the super set of:

View solution

Q. Savitch theorem relates to which of the following:

View solution

Q. The class PSPACE is closed under the following operations:

View solution

Q. Correct the given order:
NL∈ P∈ NP∈ PH∈ PSPACE

View solution

Q. NL ∈ PSPACE ∈ EXPSPACE
The given relation involves which of the following theorems?

View solution