2
Suppose we are given a set of constraints of the form $b_i \oplus b_j = c$. We construct a graph with one vertex corresponding to each $b_i$. For each constraint of the form $b_i \oplus b_j = 1$, we add an edge $\{i,j\}$. For each constraint of the form $b_i \oplus b_j = 0$, we add a new vertex $x$, and two edges $\{i,x\},\{j,x\}$.
We can think of a cut as ...
2
Showing that this your problem is in NP is easy.
To show that your problem is NP-hard, reduce from PARTITION. The reduction simply chooses a large enough modulus $k$. Details left to you.
1
Sipser reduces $A_{\mathit{TM}}$ to $\mathit{HALT}_{\mathit{TM}}$. Since $A_{\mathit{TM}}$ is uncomputable, it follows that $\mathit{HALT}_{\mathit{TM}}$ has to be uncomputable. He is using the following general statement:
If $A$ reduces to $B$ and $B$ is uncomputable, then so is $A$.
You are right that this general statement itself is proved by ...
1
Assuming you're talking about polynomial-time reductions, since PRIME is in $P$, you can reduce it to any non-trivial decision problem (for which there is at least one instance with answer YES and at least one instance with answer NO). Moreover, any problem in $P$ can be reduced to PRIME.
To reduce an instance $I$ of PRIME to an instance $I_Q$ of non ...
1
How does that guarantee that there is a hamiltonian path from s-t?
It doesn't, but the Longest Path problem doesn't require a path between particular vertices, it only requires that some simple path of length $K$ exist in the graph. To reduce Hamiltonian Path to Longest Path you just require that path to have $|V| - 1$ edges, which in a simple path must ...
Only top voted, non community-wiki answers of a minimum length are eligible
