学科分类 - 《中国大百科全书》第三版网络版

高级搜索

专业板块专题板块大众板块

总分类

返回总分类

首页

时间复杂性类/ time complexity class // time complexity class /

在图灵计算模型下依据计算时间（控制）函数的分类对可判定问题的分类。

多项式谱系PH/ polynomial hierarchy; PH /polynomial hierarchy; PH
时间复杂性类
对非确定多项式时间NP类的推广。
非确定多项式时间NP类/ nondeterministic polynomial time class NP /nondeterministic polynomial time class NP
时间复杂性类
非确定型图灵机在多项式时间可判定的问题类称为NP类。NP取自Nondeterministic Polynomial time的缩写。
多项式时间P类/ polynomial time class P /polynomial time class P
时间复杂性类
多项式时间算法求解的判定问题类，P代表多项式时间（polynomial time）。对应的函数类记为FP类或PF类。
指数时间EXP类/ exponential time class EXP /exponential time class EXP
时间复杂性类
能用指数时间（exponential time）算法求解的问题类。