决定性问题

决定性问题
image
在可计算性理论与计算复杂性理论中，所谓的决定性问题(Decision problem)是一个在某些形式系统回答是或否的问题。例如：“给两个数字x与y，x是否可以整除y？”便是决定性问题，此问题可回答是或否，且依据其x与y的值。

综述介绍

决定性问题在数学问题是否“可决定”中出现，即是否存在有效方法判定一个性质的存在性。数学中许多重要的问题都是不可决定的。
决定性问题与功能性问题(Function problem)（或复杂型问题）密切相关，功能性问题的答案内容，较简单的是比“与非”复杂很多。范例问题：“给予一个正整数x，则哪些数可整除x？”
决定性问题只有是-否两种输出