文章目录
一、coNP 类
二、coNP 完全
三、P、NP、coNP 相互关系
一、coNP 类
如果 语言 L \rm LL 在 c o N P \rm coNPcoNP 中 , 那么 该语言的补集在 N P \rm NPNP 中 ;
c o N P \rm coNPcoNP 示例 :
布尔逻辑 p \rm pp 是重言式 , 由 重言式 所组成的语言 称为 T A U T \rm TAUTTAUT ,
T A U T \rm TAUTTAUT 语言就是在 c o N P \rm coNPcoNP 中 ;
符号化表示 : T A U T = { < p > : p 是 重 言 式 } \rm TAUT = \{ <p> : p 是重言式 \}TAUT={<p>:p是重言式}
T A U T \rm TAUTTAUT 语言的 补集 , 如果不是重言式 , 那就意味着 存在这一个赋值 , 使得布尔逻辑 p \rm pp 为假 , 这个计算问题是 N P \rm NPNP 的 ;
重言式 是 永真式 , 矛盾式 是 永假式 ;
二、coNP 完全
上述 T A U T \rm TAUTTAUT 语言 是 c o N P \rm coNPcoNP 完全的 ;
c o N P \rm coNPcoNP 完全 :
① 计算问题 在 c o N P \rm coNPcoNP 中 ;
② c o N P \rm coNPcoNP 中 任何计算问题 , 都可以在 多项式时间内规约 到该计算问题中 ;
三、P、NP、coNP 相互关系
c o N P \rm coNPcoNP 与 N P \rm NPNP 是交叉的 , 但 二者之间没有包含关系 ,
P \rm PP 在 c o N P \rm coNPcoNP 与 N P \rm NPNP 交集部分 ,
N P \rm NPNP 完全 是在 N P \rm NPNP 中除 " c o N P \rm coNPcoNP 与 N P \rm NPNP 交集 " 之外的部分中 ;
c o N P \rm coNPcoNP 完全 是在 c o N P \rm coNPcoNP 中除 " c o N P \rm coNPcoNP 与 N P \rm NPNP 交集 " 之外的部分中 ;
计算问题的计算复杂度 不只是有 P \rm PP , N P \rm NPNP , N P \rm NPNP 完全 , 三类 ;
从上述 P \rm PP , N P \rm NPNP , N P \rm NPNP 完全 三个复杂类出发 , 可以得到不同的复杂类 ;
使用全程量词 , 存在量词 , 交替使用 , 定义不同的复杂类 ;
可以定义无穷多复杂类 ;
计算理论只关注 P \rm PP , N P \rm NPNP , N P \rm NPNP 完全 三个复杂类 , 这是三个最基本的复杂类 , 通过三个基本复杂类可以衍生无数个复杂类 ;
