跳转到内容

低 (复杂度)

维基百科,自由的百科全书

计算复杂度理论内,若有A与B两个复杂度类,且AB = A;或者说, A 在B成为他的神谕之后的复杂度等同于A,则我们说复杂度类别B比A要来的""。这陈述代表着一个可以解决问题类别A的机器,在获得了在单位时间内解决问题类别B的能力之后,并没有增加多余的计算能力。特别是,这代表着如果B类别低于A类别,则B必然包含在A里面。

较不正式的说,较低的关系不仅仅代表包含于B的问题可以被能够解决A问题的机器所解决, 而且是"可以被简单解决的"。一个能解决A问题类别的机器可以模拟许多计算B的启示,而不超出其计算能力的上限值。

建立在一个类别低于另一类别的关系跟结果常常被称呼为"lowness results"。