3.1 算法与问题复杂性理论

3.1 算法与问题复杂性理论
	• 一个问题可解 means 存在一个算法可以解决这个问题的所有实例
	• 复杂性
		○ ($max\left\{\left(T,S\right)\right\}$)
		○ Big O 符号，描述一个上届，表示复杂度的数量级
		○ 一般认为，指数时间的算法，在计算上不可行
	• 图灵机
		○ 无限读写能力的有限状态机
		○ 作为算法复杂度的标准
分类
确定性图灵机
非确定性图灵机
		○ 一个问题的复杂性由该问题在图灵机上解决所需的最小空间和时间复杂度
	• P问题
		○ 确定性图灵机在多项式时间内可解
	• NP问题
		○ 非确定性图灵机在多项式时间内可解
猜测
多项式时间内验证
		○ NPC问题
			§ If ($Q \in NP \forall R \not= Q \in NP$) with ($R PT~ Q$)