Support vector machines (SVMs) are classic binary classification algorithms and have been shown to be a robust and well-behaved technique for classification in many real-world problems. However, there are ambiguities in the basic concepts of SVMs although these ambiguities do not affect the effectiveness of SVMs. Corinna Cortes and Vladimir Vapnik, who presented SVMs in 1995, pointed out that an SVM predicts through a hyperplane with a maximal margin. However existing literatures have two different definitions of the margin. On the other hand, Corinna Cortes and Vladimir Vapnik converted an SVM into an optimization problem that is much easier to solve. Nevertheless, existing papers do not explain how the optimization problem derives from an SVM well. These ambiguities may cause certain troubles in understanding the basic concepts of SVMs. For this purpose, this paper defines a separating hyperplane of a training data set and, hence, an optimal separating hyperplane of the set. The two definitions are reasonable since this paper proves that ${\text{w}}_0^{\text{T}}\text{x}+b_0=0$ is an optimal separating hyperplane of a training data set when ${\text{w}}_0$ and $b_0$ constitute a solution to the above optimization problem. Some notes on the above margin and optimization problem are given based on the two definitions. These notes should be meaningful for clarifying the basic concepts of SVMs.

A (1,0)-super solution is a satisfying assignment such that if the value of any one variable is flipped to the opposite value, the new assignment is still a satisfying assignment. Namely, every clause must contain at least two satisfied literals. Because of its robustness, super solutions are concerned in combinatorial optimization problems and decision problems. In this paper, we investigate the existence conditions of the (1,0)-super solution of $(k,s)$ -CNF formula, and give a reduction method that transform from k-SAT to (1,0)- $(k+1,s)$ -SAT if there is a ( $k+1,s$ )-CNF formula without a (1,0)-super solution. Here, $(k,s)$ -CNF is a subclass of CNF in which each clause has exactly k distinct literals, and each variable occurs at most s times. (1,0)- $(k,s)$ -SAT is a problem to decide whether a $(k,s)$ -CNF formula has a (1,0)-super solution. We prove that for $k>3$ , if there exists a $(k,s)$ -CNF formula without a (1,0)-super solution, (1,0)- $(k,s)$ -SAT is NP-complete. We show that for $k>3$ , there is a critical function $\phi \left(k\right)$ such that every $(k,s)$ -CNF formula has a (1,0)-super solution for $s\le \phi \left(k\right)$ and (1,0)- $(k,s)$ -SAT is NP-complete for $s>\phi \left(k\right)$ . We further show some properties of the critical function $\phi \left(k\right)$ .