Hardness of Mathematical Problems.
When discussing hardness of mathematical problems with input some integer $N$, we study asymptotics in terms of the input length.
Integer $N$ will be assumed to be represented in binary. The running time of an algorithm taking as input an integer $N$ is measured in terms of $||N||$, the length of the binary representation of $N$.
Note that $||N||=\lfloor \log N \rfloor+1$.
A problem is considered to be easy if the running time of its algorithm is polynomial in $||N||$.
这里对数学问题困难性 (hardness) 的定义是建立在算法数论 (algorithmic number theory) 的视角上的。
实际上，这个概念更贴近计算机领域而不是纯数学领域。如果从算法时间复杂度的角度来定义，就好理解多了：一个时间复杂度为 $O(\mathtt{poly}(n))$ 的算法是高效 (efficient) 的，对应的问题是简单 (easy) 的。而时间复杂度为 $O(\mathtt{exp}(n))$ 的算法是低效 (inefficient) 的，对应的问题是困难 (hard) 的。