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

算法复杂度分类多达数百种，但它们之间许多有包含的关系。以下这组复杂度，从简单到复杂，有点像俄罗斯套娃，层层嵌套：它们是：P问题,NP问题，PH问题，多项式空间问题，指数时间问题。其中之前的每一个都是后面的复杂度的子集，但除NP与PH问题外，其他每两种复杂度之间是否是“真子集”（即，是否可以排除“等于”）关系，都还未证明。以下这组复杂度，也构成一组“套娃”：P问题，BPP问题，BQP问题。科学家认为BQP问题，即量子计算机能快速处理的问题，虽然含有很多NP问题，但与NP问题互不包含。但这仍然是待证明的领域。