计算复杂性

纵观历史，人们对在有限的步骤内从一组输入中产生一个输出这一过程具有模糊的概念，他们认为“计算”是一个人遵循某些规则随意进行的过程。20世纪前50年中一个重要的科学进步就是“计算”这个概念获得了更为准确的定义。基于这个定义，计算可能发生在各种物理及数学系统中，这一点很快就变得很明确。