Tripartite Matching is the problem defined as follows . Given an integer n, three disjoint sets A, B,C each having size n, and a set SCAx B x C (that is, a set of triples of the form (a, b, c) such that a E A, b ? B, and c E C), decide if there is a subset T of S in which each member of A. B, and C appears exactly once. This is an abstraction of the following problem: There are some n people, n cars, and n houses. Each person has a list of preferred combination of a car to drive and a house to live. Is there way to assign the cars and houses to the people so that everyone gets one of her favored combinations? Show that Tripartite Matching is in NP. (It is in fact NP-complete, but we do not prove completeness.) Tripartite Matching is the problem defined as follows . Given an integer n, three disjoint sets A, B,C each having size n, and a set SCAx B x C (that is, a set of triples of the form (a, b, c) such that a E A, b ? B, and c E C), decide if there is a subset T of S in which each member of A. B, and C appears exactly once. This is an abstraction of the following problem: There are some n people, n cars, and n houses. Each person has a list of preferred combination of a car to drive and a house to live. Is there way to assign the cars and houses to the people so that everyone gets one of her favored combinations? Show that Tripartite Matching is in NP. (It is in fact NP-complete, but we do not prove completeness.)