How many steps are required to prove that a decision problem is NP com – InterviewSolution

InterviewSolution

1.	How many steps are required to prove that a decision problem is NP complete?(a) 1(b) 2(c) 3(d) 4
Answer» Right option is (b) 2 Easiest explanation - First, the problem should be NP. Next, it should be proved that every problem in NP is reducible to the problem in question in polynomial time.

Discussion

No Comment Found

Related InterviewSolutions

What is the minimal Hamming distance between any two correct codewords?(a) 1(b) 2(c) 3(d) 4
What is the message length ‘k’ of a Hamming(7,4) code?(a) 2^r-1(b) 2^r-r+1(c) 2^r-r-1(d) 2^r+1-r
What is the total block length ‘n’ of a Hamming code?(a) 2^r(b) 2^r-1(c) 2^r-1-1(d) 2^r+1
Who invented Hamming codes?(a) Richard Hamming(b) Ross Hamming(c) Shannon(d) Huffman
A two-out-of-five code consists of _________(a) Two 0s and three 1s(b) Three 0s and two 1s(c) Four 0s and one 1s(d) One 0s and four 1s
Halting problem is an example for?(a) decidable problem(b) undecidable problem(c) complete problem(d) trackable problem
________ is the mechanism of sending data bits multiple times to ensure consistency.(a) Repetition(b) Duplication(c) Mirroring(d) Redundancy
To which of the following class does a CNF-satisfiability problem belong?(a) NP class(b) P class(c) NP complete(d) NP hard
How many steps are required to prove that a decision problem is NP complete?(a) 1(b) 2(c) 3(d) 4
Problems that cannot be solved by any algorithm are called?(a) tractable problems(b) intractable problems(c) undecidable problems(d) decidable problems