For both a) and b) you agree that if I find a generic training set and prove that there does not exist an alpha such that the formula you wrote equals 0, then I proved that given a generic training set $(x_1,y_1), \dots,(x_m,y_m) \in \{0,1\}^n \times \{0,1\}$ there does not necessarily exist a vector $\alpha \in \mathbb R^m$ such that:
$$
\sum \limits_{j=1}^m \left( \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) - y_j\right)^2 = 0
$$
?
You agree that if I prove that there does not necessarily exist such an alpha for a) then there does not necessarily exist such an alpha for b)? Just use the same training set provided for a) as for b).
So here is a generic training set:
$((1,0,0),(0)) , ((1,1,0),(1)), ((1,1,1),(1))$ where the first 3 numbers are an x and the second number in the parentheses is its corresponding y. Now lets compute all $K(x_i, x_j)$ for all i,j : $K_a(x_1 , x_1)= (1 + 1 + 0)(1 + 0 + 1)(1 + 0 + 1) = 8$, $K_a(x_1 , x_2)= (1 + 1 + 0)(1 + 0 + 0)(1 + 0 + 1) = 4$, $K_a(x_1 , x_3)= (1 + 1 + 0)(1 + 0 + 0)(1 + 0 + 0) = 2$, $K_a(x_2 , x_2)= (1 + 1 + 0)(1 + 2 + 0)(1 + 0 + 1) = 8$, $K_a(x_2 , x_3)= (1 + 1 + 0)(1 + 1 + 0)(1 + 0 + 0) = 4$ , $K_a(x_3 , x_3)= (1 + 1 + 0)(1 + 1 + 0)(1 + 1 + 0) = 8$ . Is this correct?
Now for there to exist an $\alpha$ s.t. $\sum \limits_{j=1}^m \left( \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) - y_j\right)^2 = 0$ since $\left( \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) - y_j\right)^2$ is always greater than or equal to 0, we need it to be equal to zero for every single j. i.e. we need to show that :
$\forall j$ we have $ \left( \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) - y_j\right) = 0 \implies \sum \limits_{i=1}^m \alpha_i K_a(x_i, x_j) = m * y_j$
So now consider the generic training set I provided. we need
$\sum \limits_{i=1}^m \alpha_i K_a(x_i, x_1) = 0$ since $y_1$ is 0. Since the $K_a(x_i, x_1) > 0$ we need all of the alphas to be equal to zero. Ok so we set all of the alphas to zero.
But now consider $\sum \limits_{i=1}^m \alpha_i K_a(x_i, x_2) = 3$ (since $y_2$ is 1). We need now a different set of alphas for this equation to work. So we do not have an alpha which causes this equation to be zero.
If your question is a homework question and there are no mistakes in it, then it seems I am missing something, because then it would not make sense to ask a part b.
EDIT:
Does this question relate to the represntor theorem? The representor theorem tells us that the optimal solution to Kernel SVM has the form $w = \sum \limits_{i=1}^m \alpha_i \psi (x_i) $ which if you then plug into the form of the prediction which is $\langle w, x \rangle $ you get that a prediction has the form $\sum \limits_{i=1}^m \alpha_i K_a(x_i, x)$ on some input x . So the question is asking you to figure out whether the optimal solution is necessarily perfect, i.e. 0 error. I would imagine that in some cases the answer is yes and in some cases the answer is no. This question does not make sense to me because it seems unnecessary to ask both a) and b) if a) is not true. It would make more sense if a) was true and b) wasn't. Right now as the question is asked, it doesn't seem to directly relate to linear separability or DNF. Perhaps if the question was a) also had the condition that y was the output of a DNF formula applied to x, then it would. Or if in b) it was asking to assume the training set is linearly seperable. Then perhaps the question would make sense and be more interesting, although i have not thought about it too much.
