For the reasons outlined in my comment above, i'll focus on the third part of your question.
In its most general statement, for a given admissible kernel function $k_{\lambda}(.,.)$, you can rewrite the SVM problem, in dual form, as a convex minimization one:
$$\underset{\alpha_i\geq 0, i = 1, \dots, n}{\arg.\min}\;\;\;L(\mathbf{\alpha}|X,\bf{y},\lambda)$$
where
$$L(\mathbf{\alpha}|X,\bf{y},\lambda)=\frac{1}{2}\sum_{i, j} \alpha_i \alpha_j y_i y_j k_{\lambda}(\mathbf{x}_i, \mathbf{x}_j)-\sum_{i=1}^n \alpha_i$$
If $\bf{x}_i\in\mathbb{R}^p$ and $\bf{y}\in[0,1]^n$, in general, the maximum complexity of solving such a QP can potentially be of order $O(pn^3)$. But this may not be very relevant. In most cases the average complexity will be much lower --potentially of order $O(pn^2)$-- if one uses clever algorithm designed to take advantage of properties specific to the SVM problem.
The first example is Platt's SMO algorithm (1). It is primilarly based on the observation that the problem can be solved by a series of sequential minimization of the partial objective function:
$$(a)\;\;\;\underset{\alpha_i\geq 0|\alpha_j, j\neq i}{\arg.\min}\;\;\;L(\alpha_i|X,\mathbf{y},\lambda)$$
and the idea that once one of the $k_{\lambda}(\mathbf{x}_i, \mathbf{x}_j)$ has been computed to solve (a), it can be stored so it doesn't have to be computed again.
While these two observations are potentially true for any QP, they yield particularly strong gains in the SVM context because, in a nutshell, most of the $k_{\lambda}(\mathbf{x}_i, \mathbf{x}_j)$ are negligible.
Over time, more clever tricks have been developed again, potentially lowering average complexities (e.g. 2) but the most important take away is that, often, solving even the non linear kernel SVM problem is quiet feasible.
(1) Platt (2008). Microsoft Research. Technical Report MSR-TR-98-14.
(2) Keerthi, Shevade, Bhattacharyya Murthy (2001). Improvements to Platt's SMO Algorithm for SVM Classifier Design.