P and NP,Decidable and RE
递归语言和递归可枚举语言
递归语言(decidable)要求存在一个满足如下要求的图灵机:
- Halt on accept
- Halt on reject
但是递归可枚举语言(RE:Recursive enumerable)要求存在的图灵机只需要满足: - Halt on accept
换言之,对于 True RE可能存在某个句子,你不知道这个句子在图灵机上会不会停机
正规定义:
- 递归可枚举语言是指由图灵机定义的语言(不管是通过终止状态接受还是通过停机接受)
- 递归语言:
- 定义算法是一个图灵机,该图灵机通过终止状态接受,并且无论接受与否,它都注定会停机
- 定义递归语言是由
定义的,且 是一个算法
可判定性
对于图灵可判定和图灵可识别,这两个概念如下:
- 如果一个语言是 递归语言 那么这个语言是 图灵可判定语言
- 如果一个语言是 递归可枚举语言 那么这个语言是 图灵可识别语言
非递归可枚举语言
这种类型的语言是存在的,因为RE的集合是可数集合,但是所有语言的集合的势势不可数的
P 和 NP
P 是指存在一个单带、确定性的图灵机,能够在多项式时间内判定
NP是指,存在一个非确定性图灵机,能够在多项式时间内判定
注意这两者和上面的递归可枚举的区别,这里要求的都是判定,即一定是要停机的,这两个都是递归语言的子集
对于一个
对于 NP 问题有一个很重要的定理,即
如果语言
其中
该定理的意思是,如果一个问题是
规约
规约的定义
那么
可判定的规约
如果
RE的规约
如果
注意规约的方向,假设我们现在已知问题 OLD 是一个不可判定的问题,我们想证明 NEW也是一个不可判定的问题,那么思路应该是:
- 假设 NEW 是可判定的
- 使用NEW的判定机来判定OLD
- 从而证明OLD也是可判定的
- 导出矛盾,证明NEW是不可判定的
各种封闭性
交 | 并 | 补 | 拼接 | 星闭包 | 同态 | 逆同态 | |
---|---|---|---|---|---|---|---|
正则 | 是 | 是 | 是 | 是 | 是 | 是 | 是 |
CFG | 否 | 是 | 否 | 是 | 是 | 是 | 是 |
Decidable | 是 | 是 | 是 | 是 | 是 | 否 | 是 |
RE | 是 | 是 | 否 | 是 | 是 | 是 | 是 |
各种反例如下:
CFG在交下不封闭
CFG在差集下的性质
由于
递归语言在同态下不封闭
对于递归语言,如果同态是
递归可枚举语言在补集下不封闭
这是定义,因为在不接受的情况下无法知道是否停机
规约套路
对于语言的性质
准备工作如下:
- 首先,对于语言性质
找一个实例 ,例如,对于性质 接受的语言集合是无穷集合
,该实例可以是接受所有字符串
- 找到实例
的一个子集 ,使这个子集不满足性质 ,例如 接受空集
构造
在输入 时直接接受,否则进入下一步 - 如果上一步没有接受,那么运行
作为子过程,如果停机,那么 再接受
那么
那么,由于性质
- 如果
那么accept - 如果
那么reject
所以就证明了
以 $F = L = \{
首先,构造
构造
暂时不接受,也不拒绝 - 如果上一步没有接受,那么运行
作为子过程,如果停机,那么 Accept
那么
那么,由于性质
- 如果
那么accept - 如果
那么reject
所以就证明了
以 $L = \{
首先,构造
构造
接受所有形如 的字符串,如果这一步没有接受也不拒绝 - 如果上一步没有接受,那么运行
作为子过程,如果停机,那么 直接Accept
那么
那么,由于性质
- 如果
那么accept - 如果
那么reject
所以就证明了
易错点
RE转NFA
记得在星闭包的时候,去的那条边上面也要加
写RE
记得考虑有限字符串,例如,以
注意分别是RE还是递归不可枚举
看一下能不能用NTM搞出证据来accept,如果只能搞出reject的证据,那么这个不是RE