Related InterviewSolutions

• Assuming P != NP, which of the following is true ?(A) NP-complete = NP(B) NP-complete P = (C) NP-hard = NP(D) P = NP-complete(A) A(B) B(C) C(D) D
• Which of the following statements are TRUE?(1) The problem of determining whether there exists a cycle in an undirected graph is in P.(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.(A) 1, 2 and 3(B) 1 and 3(C) 2 and 3(D) 1 and 2
• Which of the following is true about NP-Complete and NP-Hard problems.(A) 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(B) The first problem that was proved as NP-complete was the circuit satisfiability problem.(C) NP-complete is a subset of NP Hard(D) All of the above(E) None of the above
• The problem 3-SAT and 2-SAT are(A) both in P(B) both NP complete(C) NP-complete and in P respectively(D) undecidable and NP-complete respectively
• Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?(A) There is no polynomial time algorithm for X.(B) If X can be solved deterministically in polynomial time, then P = NP.(C) If X is NP-hard, then it is NP-complete.(D) X may be undecidable.
• 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. Which one of the following statements is true? (GATE CS 2006)(A) R is NP-complete(B) R is NP-hard(C) Q is NP-complete(D) Q is NP-hard