arithmetic-complexity

Bit complexity model(BCM)是说每个数的size是其二进制表示下的长度,总的size是所有数的长度的和。每次计算的复杂度与操作数的size有关。

Arithmetic complexity model(ACM)是说每个数的size是1,总的size是数的个数。每次计算的复杂度是O(1)。

通常我们使用BCM。但BCM对无理数是不适用的,因为无理数没法写成有限多个bits。

这段文章是说内点法和椭圆法在BCM下才是多项式时间的,在ACM下则不保证(目前是open problem)。

关于ACM有个strongly polynomial的定义,参见http://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time