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