Problem $2$

Prove that the following problems are in NP:

COLOR: Given a set S of n numbered balls, and C$\_(1),$dotsC$\_($k$)$ be a collection of subsets

of S$.$ Is there a way to color the balls in SR$,$G C$\_($i$)$

has all its elements of the same color?

Given a graph G$=($V$,$E$),$ we call a subset SsubeV of its vertices a dominating set if

every other node in G is adjacent to some node in the subset S$.$

DOM: Given a graph G$,$ and an integer k$,$ is there a dominating set in G of size at

most k $?$

Problem $3$

Consider the following search problem:

SEARCH$-$DOUBLE$-$SAT: Given a Boolean formula, $\backslash$Phi $($x$\_(1),$dots,x$\_($n$))$ on n variables, find two

distinct satisfying assignments for $\backslash$Phi $.$

Write an equivalent decision version for the search problem.

For the suggested decision version, show that the two problems are equivalent in

complexity, i$.$e$.,$ there is a polynomial time algorithm for the search version if and

only if there is a polynomial time solution for the decision version.