Question
a.
1
b.
2
c.
3
d.
all of the mentioned
Posted under Formal Languages and Automata Theory
Engage with the Community - Add Your Comment
Confused About the Answer? Ask for Details Here.
Know the Explanation? Add it Here.
Q. A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n,...
Similar Questions
Discover Related MCQs
Q. Which of the following is a P-complete type of problem?
View solution
Q. State true or false?
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?
The given problem is P-complete.
View solution
Q. What does NP stands for in complexity classes theory?
View solution
Q. The hardest of NP problems can be:
View solution
Q. Which of the following contains NP?
View solution
Q. Travelling sales man problem belongs to which of the class?
View solution
Q. 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.
View solution
Q. A problem which is both _______ and _________ is said to be NP complete.
View solution
Q. Which of the following is incorrect for the given phrase:
'solvable by non deterministic algorithms in polynomial time'
View solution
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
Suggested Topics
Are you eager to expand your knowledge beyond Formal Languages and Automata Theory? We've curated a selection of related categories that you might find intriguing.
Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!
