2. "复杂度动物园"中的"俄罗斯套娃"

2. "复杂度动物园"中的"俄罗斯套娃"

00:00
13:52

算法复杂度分类多达数百种,但它们之间许多有包含的关系。

以下这组复杂度,从简单到复杂,有点像俄罗斯套娃,层层嵌套:它们是:P问题, NP问题,PH问题,多项式空间问题,指数时间问题。其中之前的每一个都是后面的复杂度的子集,但除NP与PH问题外,其他每两种复杂度之间是否是“真子集”(即,是否可以排除“等于”)关系,都还未证明。

以下这组复杂度,也构成一组“套娃”:P问题,BPP问题,BQP问题。

科学家认为BQP问题,即量子计算机能快速处理的问题,虽然含有很多NP问题,但与NP问题互不包含。但这仍然是待证明的领域。




以上内容来自专辑
用户评论
  • 文忠裔人

    棒极了!

  • 凯撒不说话

    支持