(Solved): Answer all parts Let X,Y and Z be decision problems. Answer True, False, or Unknown. 1. Suppose X ...

Let $X,Y$ and $Z$ be decision problems. Answer True, False, or Unknown. 1. Suppose $X{?}_p^{m}Y$. If $Y$ can be solved in polynomial time, then so can $X$. 2. If $X?\mathcal{NP}$ and $Y?/\mathcal{NP}$, then $X{z}_p^{m}Y$. 3. If $co-\mathcal{NP}=\mathcal{NP}$, then $\mathcal{P}=\mathcal{NP}$. 4. If $X$ cannot be solved in polynomial time, then $X?\mathcal{NP}$. 5. If $X$ is $\mathcal{NP}$-complete, then $X?/\mathcal{P}$. 6. Give an example of a decision problem that is not in $\mathcal{NP}$. 7. $\mathcal{NP}?\mathrm{co}?\mathcal{NP}?\mathcal{P}$. 8. Suppose $X{?}_p^{m}Y$. If $Y$ cannot be solved in polynomial time, then neither can $X$. 10. The Halting Problem is $\mathcal{NP}$-hard. 11. $\mathcal{NP}?=co-\mathcal{NP}$. 12. If $X{?}_p^{m}Y$ and $X?\mathcal{NP}$, then $Y?\mathcal{NP}$. 13. If $X?\mathcal{NP}$, then there does not exist a polynomial time algorithm for $X$. 14. The Halting Problem is $\mathcal{NP}$-complete. 15. All-Even $?\frac{m}{m}3$-SAT. 16. If $X{?}_p^{m}Y$, then $\stackrel{?}{Y}{?}_p^m\stackrel{?}{X}$. 17. 2 -SAT ${?}_p^m\overline{2?\mathrm{SAT}}$. ALL-EvEN Input: an array $A[\mathrm{1..}n]$ of non-negative integers Output: "Yes" if all $n$ integers in $A$ are even, "No" if at least one integer in $A$ is odd.