Question

Which of the following cannot be solved using polynomial time?

(a) Linear Programming

(b) Greatest common divisor

(c) Maximum matching

(d) None of the mentioned

I 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 1

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 matching  M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.