决定性问题

在可计算性理论与计算复杂性理论中，所谓的决定性问题(Decision problem)是一个在某些形式系统回答是或否的问题。例如：“给两个数字x与y，x是否可以整除y？”便是决定性问题，此问题可回答是或否，且依据其x与y的值。决定性问题在数学问题是否“可决定”中出现，即是否存在有效方法判定一个性质的存在性。数学中许多重要的问题都是不可决定的。