$2$ Demonstrating a Problem in Both NP and co$-$NP

In this problem, you will explore a specific problem that belongs to both the complexity classes NP and

co$-$NP$.$ Specifically, you will demonstrate why the Exact Cover Problem fits into both of these classes.

You will also review the definitions of NP and co$-$NP and explain how Exact Cover satisfies the conditions

for membership in both classes.

Definitions

$$ NP $($Nondeterministic Polynomial Time$)$: A decision problem is in NP if a solution $($or certificate$)$

can be verified in polynomial time. That is$,$ given a proposed solution, there exists a polynomial$-$time

algorithm that can check whether the solution is correct.

$$ co$-$NP: A decision problem is in co$-$NP if a no answer $($or a counterexample$)$ can be verified in

polynomial time. In other words, co$-$NP is the complement of NP$,$ where instead of verifying a solution,

you verify that no solution exists $($or that a counterexample is valid$).$

The problem we will focus on a somewhat easier variant of the Ordered Exact Cover Problem, which

asks the following:

$$ Input: A set U of n distinct elements and a collection S of subsets of U $.$

$$ Output: Is there a subset of S such that the union of the sets in this subset exactly covers U $,$ with no

element of U being covered more than once? That is$,$ is there a subset T $$ S such that all elements

of T are pairwise disjoint and S

t in T t $=$ U $.$

$$ Promise: The set S is ordered such that for all i$,$ i $+1,$ Si $<$ Si$+1$ iff $(1)$ Si $$ Si$+1=$ and $(2)$

max Si $<$ max Si$+1.$

Questions

$1.$ Verifying Ordered Exact Cover in NP:

$$ Show that the Exact Cover Problem is in NP by explaining how to verify a solution in poly$-$

nomial time.

$$ Specifically, describe how, given a set U and a $($polynomially bounded$)$ collection of subsets S$,$

you can provide a certificate of an exact cover $($a set of subsets whose union equals U $)$ and verify

that no element of U is covered more than once.

$$ Explain why this satisfies the definition of NP