Hamilton Circuit problem is a special case of ____________(a) travelling salesman problem(b) halting problem(c) hitting set(d) none of the mentionedI had been asked this question during an online interview.This intriguing question comes from Node-Cover Problem, Hamilton Circuit Problem topic in section Intractable Problems of Automata Theory

Hamilton Circuit problem is a special case of ____________(a) travelli

1.	Hamilton Circuit problem is a special case of ____________(a) travelling salesman problem(b) halting problem(c) hitting set(d) none of the mentionedI had been asked this question during an online interview.This intriguing question comes from Node-Cover Problem, Hamilton Circuit Problem topic in section Intractable Problems of Automata Theory
Answer» RIGHT option is (a) TRAVELLING SALESMAN problem Explanation: Hamilton circuit problem is a special case of travelling salesman problem, OBTAINED by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is EQUAL to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).

Discussion

No Comment Found

Related InterviewSolutions

State true or false:Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.(a) Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.(b) true(c) falseThe question was posed to me in an internship interview.My doubt is from Node-Cover Problem, Hamilton Circuit Problem in portion Intractable Problems of Automata Theory
Which of the following are not in NP?(a) All problems in P(b) Boolean Satisfiability problems(c) Integer factorization problem(d) None of the mentionedThis question was posed to me in semester exam.Question is from Non Deterministic Polynomial Time in portion Intractable Problems of Automata Theory
A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.(a) 1(b) 2(c) 3(d) all of the mentionedThe question was posed to me during an interview for a job.The query is from Problem Solvable in Polynomial Time topic in chapter Intractable Problems of Automata Theory
Which of the following can be used to define NP complexity class?(a) Verifier(b) Polynomial time(c) Both (a) and (b)(d) None of the mentionedThe question was asked during an internship interview.This interesting question is from Non Deterministic Polynomial Time topic in chapter Intractable Problems of Automata Theory
What does NP stands for in complexity classes theory?(a) Non polynomial(b) Non-deterministic polynomial(c) Both (a) and (b)(d) None of the mentionedThis question was addressed to me in class test.My question is from Non Deterministic Polynomial Time in section Intractable Problems of Automata Theory
The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.(a) Push Down automata(b) DFA(c) NDFA(d) Deterministic Turing machineI had been asked this question by my school teacher while I was bunking the class.Asked question is from Problem Solvable in Polynomial Time topic in division Intractable Problems of Automata Theory
Which of the following is a P-complete type of problem?(a) Circuit Value problem(b) Linear programming(c) Context free grammar membership(d) All of the mentionedThe question was posed to me in an interview.Enquiry is from Problem Solvable in Polynomial Time in chapter Intractable Problems of Automata Theory
The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.(a) Push Down automata(b) DFA(c) NDFA(d) Deterministic Turing machineThe question was asked during an interview.This is a very interesting question from Problem Solvable in Polynomial Time topic in section Intractable Problems of Automata Theory
If the number of steps required to solve a problem is O(n^k), then the problem is said to be solved in:(a) non-polynomial time(b) polynomial time(c) infinite time(d) none of the mentionedI got this question in a national level competition.Enquiry is from Problem Solvable in Polynomial Time in section Intractable Problems of Automata Theory
If the number of steps required to solve a problem is O(n^k), then the problem is said to be solved in:(a) non-polynomial time(b) polynomial time(c) infinite time(d) none of the mentionedI had been asked this question in a national level competition.My doubt is from Problem Solvable in Polynomial Time in division Intractable Problems of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment