Create Quiz

NP-Completeness Introduction - Quiz Question

NP-Completeness Introduction - Quiz Question

NP Quiz Question is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time

You can mute/unmute sounds from here

You May Get Result Of NP-Completeness Introduction - Quiz Question

NP Quiz Question is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time
NP Quiz Question is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time
NP Quiz Question is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time
NP Quiz Question is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time
POST YOUR ANSWER (READ ANSWERS)

Quiz Questions And Answers

Assuming P != NP, which of the following is true ? (A) NP-complete = NP (B) NP-complete \cap P = \Phi (C) NP-hard = NP (D) P = NP-complete

A
B
C
D

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. True is:

R is NP-complete
R is NP-hard
Q is NP-complete
Q is NP-hard

Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?

There is no polynomial time algorithm for X
If X can be solved deterministically in polynomial time, then P = NP
If X is NP-hard, then it is NP-complete.
X may be undecidable

The problem 3-SAT and 2-SAT are

both in P
both NP complete
NP-complete and in P respectively
None

Which of the following is true about NP-Complete and NP-Hard problems.

If we want to prove that a problem X is NP-Hard, we take a known NP-Hard problem Y and reduce Y to X
The first problem that was proved as NP-complete was the circuit satisfiability
NP-complete is a subset of NP Hard
All of the above
ANSWERS

Currently, we have no comments. Be first to comment on this quiz.

NP-Completeness Introduction - Quiz Question : Test Trivia

Ultimate impossible accurate personality honest Quiz Game

How do you rate this quiz?

Average rating 4.8 / 5. Vote: 5
Embed This Quiz
Copy the code below to embed this quiz