1.

Which of the following problems were reduced to Knapsack?(a) Exact Cover(b) Max Cut(c) 0-1 integer programming(d) None of the mentionedThis question was posed to me during a job interview.Asked question is from Node-Cover Problem, Hamilton Circuit Problem topic in division Intractable Problems of Automata Theory

Answer»

Right option is (a) Exact Cover

The best I can EXPLAIN: Exact cover is a DECISION PROBLEM in computer SCIENCE to DETERMINE if an exact cover exists.



Discussion

No Comment Found

Related InterviewSolutions