数学难题 — Lalande.

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||$ .

Eureka moment!

这里对数学问题困难性 (hardness) 的定义是建立在算法数论 (algorithmic number theory) 的视角上的。

实际上，这个概念更贴近计算机领域而不是纯数学领域。如果从算法时间复杂度的角度来定义，就好理解多了：一个时间复杂度为 $O(\mathtt{poly}(n))$ 的算法是高效 (efficient) 的，对应的问题是简单 (easy) 的。而时间复杂度为 $O(\mathtt{exp}(n))$ 的算法是低效 (inefficient) 的，对应的问题是困难 (hard) 的。