Can we detect perfect matchings in P? in NP? in coNP?

Question

This question concerns the classes P and N P . If you are familiar with them, you may skip the definitions and go directly to the question. Let L be a set. We say that L is in P if there is some algorithm which given input x decides if x is in L or not in time bounded by a polynomial in the length of x. For example, the set of all connected graphs is in P , because there is an algorithm which, given a graph graph, can decide if it is connected or not in time roughly proportional to the number of edges of the graph.

The class NP is a superset of class P . It contains those sets that have membership witnesses that can be verified in polynomial time. For example, the set of composite numbers is in NP . To see this take the witness for a composite number to be one of its divisors. Then the verification process consists of performing just one division using two reasonable size numbers. Similarly, the set of those graphs that have a Hamilton cycle, i.e. a cycle containing all the vertices of the graph, is in in NP. To verify that the graph has a Hamilton cycle we just check if the witnessing sequence of vertices indeed a cycle of the graph that passes through all the vertices of the graph. This can be done in time that is polynomial in the size of the graph.

More precisely, if L is a set in P consisting of elements of the form (x, w), then the set M={x:∃w,|w|≤|x|k and (x,w)∈L},

is in N P . Let G = (V, E) be a graph. G is said to have perfect matching if there is a subset M of the edges of G so that

No two edges in M intersect (have a vertex in common); and Every vertex of G has an edge in M. Let MATCH be the set of all graphs that have a perfect matching. Let ~MATCH be the set of graphs that do not have a perfect matching. Let o(G) be the number of components of G that have an odd number of vertices.

Tutte’s Theorem: G∈MATCH if and only if for all subsets S of V, the number of components in G − S (the graph formed by deleting the vertices in S) with an odd number of vertices is at most |S|. That is, G∈MATCH↔∀S⊆Vo(G−S)≤|S|. Which of the following is true?

1. MATCH∈NP and ~MATCH ∉ NP
2. ~MATCH ∈NP and MATCH ∉ NP
3. MATCH ∈ NP and ~MATCH ∈NP
4. MATCH ∉ P and ~MATCH ∉ P
5. None of the above

How to approach such type of questions ?