How many conditions have to be met if an NP- complete problem is polynomially reducible?(a) 1(b) 2(c) 3(d) 4I had been asked this question by my college professor while I was bunking the class.My query is from Checksum, Complexity Classes & NP Complete Problems topic in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

How many conditions have to be met if an NP- complete problem is polyn

1.	How many conditions have to be met if an NP- complete problem is polynomially reducible?(a) 1(b) 2(c) 3(d) 4I had been asked this question by my college professor while I was bunking the class.My query is from Checksum, Complexity Classes & NP Complete Problems topic in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
Answer» The correct choice is (b) 2 To explain: A function t that maps all yes INSTANCES of decision problems D1 and D2 and t should be COMPUTED in polynomial time are the TWO conditions.

Discussion

No Comment Found

Related InterviewSolutions

What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?(a) O(n)(b) O(sum)(c) O(n^2)(d) O(sum*n)The question was posed to me in an interview.This intriguing question originated from Checksum, Complexity Classes & NP Complete Problems in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
Which of the following is true about the time complexity of the recursive solution of set partition problem?(a) It has an exponential time complexity(b) It has a linear time complexity(c) It has a logarithmic time complexity(d) it has a time complexity of O(n2)This question was posed to me by my school teacher while I was bunking the class.The above asked question is from Checksum, Complexity Classes & NP Complete Problems topic in section Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
What is the set partition problem?(a) finding a subset of a set that has sum of elements equal to a given number(b) checking for the presence of a subset that has sum of elements equal to a given number(c) checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result(d) finding subsets with equal sum of elementsThis question was posed to me in homework.The query is from Checksum, Complexity Classes & NP Complete Problems topic in section Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
What is meant by the power set of a set?(a) subset of all sets(b) set of all subsets(c) set of particular subsets(d) an empty setThis question was addressed to me during an online interview.The doubt is from Checksum, Complexity Classes & NP Complete Problems topic in portion Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
Which of the following is true about the time complexity of the recursive solution of the subset sum problem?(a) It has an exponential time complexity(b) It has a linear time complexity(c) It has a logarithmic time complexity(d) it has a time complexity of O(n2)The question was posed to me in examination.The query is from Checksum, Complexity Classes & NP Complete Problems topic in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
What is a subset sum problem?(a) finding a subset of a set that has sum of elements equal to a given number(b) checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result(c) finding the sum of elements present in a set(d) finding the sum of all the subsets of a setThis question was posed to me by my college professor while I was bunking the class.The origin of the question is Checksum, Complexity Classes & NP Complete Problems topic in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
Under what condition any set A will be a subset of B?(a) if all elements of set B are also present in set A(b) if all elements of set A are also present in set B(c) if A contains more elements than B(d) if B contains more elements than AThis question was posed to me in an international level competition.The doubt is from Checksum, Complexity Classes & NP Complete Problems in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
How many Hamiltonian paths does the following graph have?(a) 1(b) 2(c) 0(d) 3I had been asked this question in class test.Enquiry is from Checksum, Complexity Classes & NP Complete Problems topic in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
How many Hamiltonian paths does the following graph have?(a) 1(b) 2(c) 3(d) 4The question was posed to me in my homework.My doubt is from Checksum, Complexity Classes & NP Complete Problems in section Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II
What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?(a) O(N!)(b) O(N! * N)(c) O(log N)(d) O(N)This question was addressed to me during an interview.My question is taken from Checksum, Complexity Classes & NP Complete Problems in section Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment