【计算理论】计算复杂性 ( coNP 问题 | coNP 完全 | P、NP、coNP 相互关系 )

文章目录

一、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 完全 三个复杂类 , 这是三个最基本的复杂类 , 通过三个基本复杂类可以衍生无数个复杂类 ;