gs gs101 Intractable Problems - Non Deterministic Polynomial Time - Quiz No.1
gs gs101 Automata Theory Quiz
This quiz belongs to book/course code gs gs101 Automata Theory of gs organization. We have 92 quizzes available related to the book/course Automata Theory. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Intractable Problems. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: What does NP stands for in complexity classes theory?
Non polynomial
Non-deterministic polynomial
All of the mentioned
None of the mentioned
Question 2: The hardest of NP problems can be:
NP-complete
NP-hard
P
None of the mentioned
Question 3: Which of the following contains NP?
PSPACE
EXPSPACE
Both PSPACE and EXPSPACE
None of the mentioned
Question 4: Travelling sales man problem belongs to which of the class?
P
NP
Linear
None of the mentioned
Question 6: A problem which is both _______ and _________ is said to be NP complete.
NP, P
NP, NP hard
P, P complete
None of the mentioned
Question 7: Which of the following is incorrect for the given phrase
Phrase :’solvable by non deterministic algorithms in polynomial time’
Phrase :’solvable by non deterministic algorithms in polynomial time’
NP Problems
During control flow, non deterministic algorithm may have more than one choice
If the choices that non deterministic algorithm makes are correct, the amount of time it takes is bounded by polynomial time.
None of the mentioned
Question 8: In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time.
O(n)
O(n1/2)
O(nk), k∈N
None of the mentioned
Question 9: Which of the following can be used to define NP complexity class?
Verifier
Polynomial time
Both Verifier and Polynomial time
None of the mentioned
Question 10: Which of the following are not in NP?
All problems in P
Decision version of Integer factorization method
Graph Isomorphism Problem
All NP complete problems, etc.
Online Quizzes of gs101 Automata Theory
Other Classes Of Problems - Randomized Algorithm - Quiz No.1
gs gs101
Automata Theory Online Quizzes
Push Down Automata - DPDA and Ambiguous Grammars - Quiz No.1
gs gs101
Automata Theory Online Quizzes
