I have 10 operators, let's call them p, p^t, k1^t, k2^t, k3, k4, l1^t, l2^t, l3, l4. I want pair operators without ^t with operators with ^t such that 5 pairs result. There are many ways to do so, however I have certain rules I want them to follow:

I want to pair p with k1^t or k2^t and p^t with l3 or l4 or the other way around.
The remaining of k1^t or k2^t can only be paired with the remaining l3 or l4.
The remaining ks have to be paired with ls, e.g. k3 with l1^t and k4 with l2^t.

If I'm not mistaken, there are a total of 16 ways to pair them. I am too lazy to write down all possible p…

Hello!!
Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete.

Hint:Use the exact cover problem.



The exact cover problem is the follwing:
Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a set cover consisting of a subfamily of pairwise disjoint sets?
First of all, to show that this problem is in $\mathcal{NP}$ do we have to do the following??


A nondeterministic Turing machine can first guess which the subsequence of that we are looking for is and…