典型文献
关于在线性条件下NP≠P的证明
文献摘要：
本文证明了逻辑公式中所含有的辑门的总个数是否可转化为多项式的等价于逻辑公式中所含有的自由变元总次数是否可转化为多项式的.从而利用逻辑公式中所含有的自由变元总次数,来判断P类与NP类问题.针对NP中的类皇后问题Simqueen(n),证明了Simqueen(n)的在线性条件下非单调电路复杂度是不可能为多项式的,从而说明Simqueen(n)在线性条件下不是一个P类问题.最后得到了在线性条件下NP≠P.
文献关键词：
析取范式;P类与NP类问题;非单调电路复杂度;Simqueen(n)
中图分类号：
作者姓名：
樊雪双;李云娟
作者机构：
西安思源学院基础部 陕西西安 710038;玛普阿大学研究生院 菲律宾马尼拉 999005
文献出处：
引用格式：
[1]樊雪双;李云娟-.关于在线性条件下NP≠P的证明)[J].科技风,2022(21):23-25,104
A类：
Simqueen,非单调电路复杂度
B类：
NP,所含,可转化,多项式,等价,皇后,析取范式
AB值：
0.164842
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
