Automata Theory Multiple Choice Questions on “Non Deterministic Polynomial Time”.
1. What does NP stands for in complexity classes theory?
a) Non polynomial
b) Non-deterministic polynomial
c) Both (a) and (b)
d) None of the mentioned
Answer: b
Clarification: NP is said to be one of the most fundamental complexity classes. NP is an acronym for Non deterministic polynomial time.
2. The hardest of NP problems can be:
a) NP-complete
b) NP-hard
c) P
d) None of the mentioned
Answer: a
Clarification: NP class contains many important problems, the hardest of which is NP-complete, whose solution is sufficient to deal with any other NP problem in polynomial time.
3. Which of the following contains NP?
a) PSPACE
b) EXPSPACE
c) Both (a) and (b)
d) None of the mentioned
Answer: c
Clarification: It is sufficient to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial time verifier. It is also contained in EXPTIME, since the same algorithm operates in exponential time.
4. Travelling sales man problem belongs to which of the class?
a) P
b) NP
c) Linear
d) None of the mentioned
Answer: b
Clarification: Travelling Salesman Problem: Given an input matrix of distances between n cities, this problem is to determine if there is a route visiting all cities with total distance less than k.
5. State true or false?
Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP.
a) true
b) false
Answer: a
Clarification: This is just a commutative property of NP complexity class where a problem is said to be in NP if it can be solved using an algorithm which was used to solve another NP problem in polynomial amount of time.
6. A problem which is both _______ and _________ is said to be NP complete.
a) NP, P
b) NP, NP hard
c) P, P complete
d) None of the mentioned
Answer: a
Clarification: A problem is said to be NP Hard if an algorithm for solving the problem can be translated from for solving any other problem. It is easier to show a problem NP than showing it Np Hard.
7. Which of the following is incorrect for the given phrase
Phrase :’solvable by non deterministic algorithms in polynomial time’
a) NP Problems
b) During control flow, non deterministic algorithm may have more than one choice
c) If the choices that non deterministic algorithm makes are correct, the amount of time it takes is bounded by polynomial time.
d) None of the mentioned
Answer: d
Clarification: Primality testing is a simple example. To decide whether a number is prime or not, one simply selects non deterministically a number checks whether factors exist for the number or not.
8. 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(n1/2)
c) O(nk), k∈N
d) None of the mentioned
Answer: c
Clarification: The complexity class NP can be defined in terms of NTIME as:
NP=O(nk) for k ∈N.
9. Which of the following can be used to define NP complexity class?
a) Verifier
b) Polynomial time
c) Both (a) and (b)
d) None of the mentioned
Answer: c
Clarification: NP can be defined using deterministic turing machines as verifiers.
10. Which of the following are not in NP?
a) All problems in P
b) Boolean Satisfiability problems
c) Integer factorization problem
d) None of the mentioned
Answer: d
Clarification: This is a list of some problems which are in NP:
a) All problems in P
b) Decision version of Integer factorization method
c) Graph Isomorphism Problem
d) All NP complete problems, etc.
11. Which of the following does not belong to the closure properties of NP class?
a) Union
b) Concatenation
c) Reversal
d) Complement
Answer: d
Clarification: It is unknown about the closure property-complement for the complexity class NP. The question is so called NP versus co-NP problem.