关于在线性条件下NP≠P的证明  

作　　者：樊雪双[1,2] 李云娟 

机构地区：[1]西安思源学院基础部,陕西西安710038 [2]玛普阿大学研究生院,菲律宾马尼拉999005

出　　处：《科技风》2022年第21期23-25,104,共4页

摘　　要：本文证明了逻辑公式中所含有的辑门的总个数是否可转化为多项式的等价于逻辑公式中所含有的自由变元总次数是否可转化为多项式的。从而利用逻辑公式中所含有的自由变元总次数,来判断P类与NP类问题。针对NP中的类皇后问题Simqueen(n),证明了Simqueen(n)的在线性条件下非单调电路复杂度是不可能为多项式的,从而说明Simqueen(n)在线性条件下不是一个P类问题。最后得到了在线性条件下NP≠P。

关 键 词：析取范式 P类与NP类问题 非单调电路复杂度 Simqueen(n) 

分 类 号：O141[理学—数学]