question archive a) Let Composites be the following problem
a) Let Composites be the following problem
Subject:Computer SciencePrice: Bought3
a) Let Composites be the following problem.
Input: An n-bit integer m.
Question: Is m a composite, that is a non-trivial product of two integers; in other words are there integers r and s, with r, s 6= 1, where m = rs?
Show that Composites has a polynomial time checker. Comment. Interestingly, there is a polynomial time algorithm (called a primality test) to test this property; however this algorithm does this without identifying a pair r and s of divisors for m.
b. Graph Isomorphism Input: Two undirected graphs G = (V, E) and H = (W, F), having equal numbers of vertices and edges.
Question: Is there an isomorphism of G with H, i.e. can the vertices of V be mapped oneto-one to the vertices of H in such a way that each edge in G is mapped to an edge of H?
Show that Graph Isomorphism has a polynomial time checker.
