This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Non Deterministic Polynomial Time”.
1. What does NP stands for in complexity classes theory?
a) Non polynomial
b) Non-deterministic polynomial
c) All of the mentioned
d) None of the mentioned
View Answer
Explanation: 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
View Answer
Explanation: 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 PSPACE and EXPSPACE
d) None of the mentioned
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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 Verifier and Polynomial time
d) None of the mentioned
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: It is unknown about the closure property-complement for the complexity class NP. The question is so called NP versus co-NP problem.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Automata Theory Books
- Apply for Computer Science Internship
