可判定性和复杂性
首先，我们所有的计算机的理论模型可以抽象成图灵机（Turing Machine）的形式，即图灵机的计算能力就能够代表实际计算机的计算能力了，然后我们就可以使用图灵机来研究可判定性和复杂性的问题。
可判定性（Decidable）的问题可以说是计算理论中最具哲学意义的定理之一。计算机看上去是如此的强大，以至于使得人们相信所有的问题最终都将屈服于它们。但是，不幸的是，这个世界上存在着很多计算机不能解决的问题，即计算机不可判定(Undecidable）。在逻辑里面，如果某个推理是不可判定的，即表明对它的判断过程是不能停机的，该推理过程将一直运行下去，永远都不会停止。
如果某个问题是可判定的，那么对该问题的计算的分析就进入了复杂性分析的领域，一个比可判定性更为复杂的领域。复杂性分析的原因在于问题的求解需要计算资源（时间和存储量），某些问题即使是可解的（可判定的），但是也许由于其需要过多的计算资源而变得不可解（在实际的情况中无法应用，比如说需要一亿年的时间）。根据计算资源的不同，我们把复杂度分为时间复杂性和空间复杂性两种。
在时间复杂性中，根据计算时间增长速率的不同，将其分为两大类，P问题和NP问题。P问题是单带图灵机在多项式时间内可判定的语言类。NP问题的准确定义是具有多项式时间验证的语言类，从判定的角度说，它是非确定性图灵机在多项式时间内判定的语言类，求解NP问题的最好方法是确定性的使用指数级的时间(EXPTIME)。他们之间的关系如：P属于NP属于EXPTIME。这里要提及的几个相关的问题，第一，存在着一个CoNP的语言类，它表示NP中的补语言，即不可在多项式时间内验证的语言类；第二，如果一个算法是多项式时间内可解的，那么可以说该算法是“快速”可解的，也就是说，在实际应用中，我们需要时间复杂度不超过多项式时间可解的算法；第三，在NP问题内，存在着一类非常重要的问题，叫做NP完全的（NP-complete），这类问题是相互联系在一起（使用多项式时间的算法可以相互转化）的，即如果某一个问题解决了，该类问题就解决了。NP完全问题是最难解的一类问题。
对照着时间复杂性，空间复杂性可分为PSPACE和NPSPACE问题。PSPACE是在确定型图灵机上，在多项式空间可判定的语言。NPSPACE问题是在非确定性图灵机上，在多项式空间可判定的语言。由于空间的可重用性（与时间的最大的不同点），并根据萨维奇定理，可知PSPACE问题和NPSPACE问题是相等的。
下面来看看空间复杂性和时间复杂性之间的关系，根据图灵机模型，可以知道每个计算至多能访问一个新的单元，也就是说在多项式时间内可解得问题最多只能消耗多项式的空间，即P问题属于PSPACE问题，NP问题属于NPSPACE的问题。总结起来，得到下面的关系，P属于NP属于PSPACE等于NPSPACE属于EXPTIME
虽然在上文中，提到了算法最好是在多项式时间内可解的，但是在实际的情况中，存在着大量的NP的有价值的问题。对于这些问题，一般的处理方法有两种思路，如果它不是NP-complete问题，或许可以找到解决该问题的关键点，从而将NP问题转化成P问题；第二种方法是，采取近似的方法，牺牲部分的准确度来换取效率的提高。
想想描述逻辑中的推理问题，虽然现在OWL-DL中，推理问题被证明是指数级的，但是还是能在实际情况中应用。究其原因，我猜想主要是大部分的应用情况下，计算规模不会很大，并不会花费多少时间。现实的问题是复杂的，并不仅仅由复杂性的分析就可以断定的。关于逻辑推理的复杂性，是我关心的问题，等下次好好研究后再写心得。
