单一数字系统

与标准的位置数字系统相比,单数系统很不方便,因此在实践中不用于大型计算。它出现在理论计算机科学中的一些决策问题描述中(如一些P-complete问题),它被用来人为地减少问题的运行时间或空间要求。例如,整数分解问题被怀疑需要超过输入长度的多项式函数作为运行时间,如果输入是二进制的,但如果输入是单进制的,它只需要线性运行时间。然而,这有可能是误导。对于任何给定的数字来说,使用单数输入都比较慢,而不是更快;区别在于二进制(或更大的基数)输入与数字的基数2(或更大的基数)对数成正比,而单数输入则与数字本身成正比。

单一数字系统

因此,虽然单数的运行时间和空间要求作为输入大小的函数看起来更好,但它并不代表一个更有效的解决方案。在计算复杂性理论中,单数被用来区分强NP不完全的问题和NP不完全但不是强NP不完全的问题。如果一个问题的输入包括一些数字参数,即使通过用单数表示参数使输入的大小人为地变大,它仍然是NP-完全的,那么这个问题就是强NP-完全的。对于这样的问题,存在着所有参数值最多是多项式大的硬实例。

单一数字系统的应用

单数编号被用作一些数据压缩算法的一部分,如Golomb编码。它也构成了Peano公理的基础,用于在数理逻辑中实现算术的形式化。一种被称为Church编码的单数符号被用于在lambdacalculus中表示数字。

0

点评

点赞

相关文章