Which of the following cannot be solved using polynomial time?(a) Linear Programming(b) Greatest common divisor(c) Maximum matching(d) None of the mentionedI had been asked this question in homework.This interesting question is from Problem Solvable in Polynomial Time in division Intractable Problems of Automata Theory

Which of the following cannot be solved using polynomial time?(a) Line

1.	Which of the following cannot be solved using polynomial time?(a) Linear Programming(b) Greatest common divisor(c) Maximum matching(d) None of the mentionedI had been asked this question in homework.This interesting question is from Problem Solvable in Polynomial Time in division Intractable Problems of Automata Theory
Answer» RIGHT ANSWER is (d) None of the mentioned The best explanation: In graph theory, a matching or independent edge set in a graph G is a set of edges WITHOUT common vertices. Given a graph (V, E), a matchingM in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.

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