Automata Theory Questions and Answers – Non Deterministic Polynomial Time

«
»

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

Answer: b
Explanation: NP is said to be one of the most fundamental complexity classes. NP is an acronym for Non deterministic polynomial time.
advertisement

2. The hardest of NP problems can be:
a) NP-complete
b) NP-hard
c) P
d) None of the mentioned
View Answer

Answer: a
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

Answer: c
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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

4. Travelling sales man problem belongs to which of the class?
a) P
b) NP
c) Linear
d) None of the mentioned
View Answer

Answer: b
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

Answer: a
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.
advertisement

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

Answer: a
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

Answer: d
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.
advertisement

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

Answer: c
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

Answer: c
Explanation: NP can be defined using deterministic turing machines as verifiers.
advertisement

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

Answer: d
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

Answer: d
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.