计算决策性问题的一种性质，指在非确定性杜林机求解决策性问题，其求解所需的步骤和输入资料的大小成多项式函数的关系者。非确定性的意思为产生该问题所有的可能解，再以试误法一一检验。虽然检验一可能解可在多项式时间完成，但整个检验可能需用指数时间才能完成工作。参【决策问题】（decision problem）。